Problem D. Diversify start positions ≡

Statement

New Vasuki Challenge (NVC) is a race developed to make New Vasuki a new racing capital of the world. An outstanding feature of NVC is the distribution of start positions.

Let n be the number of cars taking place in NVC during the whole season. Each car has its id — integer number in range from 1 to n. A season consists of x races. Before a race each car takes a start position. There are n start positions, numbered from 1 to n.

In the beginning of a new season NVC director declares a permutation P = (p₁, p₂, …, p_n). Before the first race car number i takes start position number i for each i from 1 to n. Before each next race start positions are permuted according to P: car which was on start position p_i in the last race now goes to start position i.

Say, n = 6, x = 3, P = (4, 3, 6, 5, 1, 2). So, there will be three races and cars will stand in positions (1, 2, 3, 4, 5, 6) before the first race, (4, 3, 6, 5, 1, 2) before the second race, and (5, 6, 2, 1, 4, 3) before the third race.

A permutation P of size n is called feasible for given x iff:

• start position distributions are different for each race;
• it's impossible to increase the number of races x without breaking the first rule;
• each car changes its position after the permutation.

For the example given above, (4, 3, 6, 5, 1, 2) is feasible because all three start position distributions are different, and if there were a forth race the distribution would be (1, 2, 3, 4, 5, 6) which already met in the first race.

Your task is to find a feasible permutation P for given n and x. If there are multiple solutions, output any of them.

Input file format

Input file contains two integers n and x.

Output file format

Output file must contain a feasible permutation. If a feasible permutation doesn't exist, output a single integer  − 1.

Constraints

2 ≤ n ≤ 10³

2 ≤ x ≤ 10⁶

Sample tests

6 3

4 3 6 5 1 2

Explanation

Переформулируем задачу. Необходимо сгенерировать перестановку P порядка n. Условия, которые накладываются на перестановку P таковы:

• перестановки I, P, P², …, P^x должны быть различны;
• перестановка P^x + 1 совпадает с одной из I, P, P², …, P^x;
• перестановка P не содержит неподвижных точек.

Рассмотрим циклы перестановки P. Обозначим их длины через n_i, а их количество через k. То есть, n₁ + …  + n_k = n. Каждое очередное применение перестановки сдвигает циклы. Перестановка P, применённая к единичной n_i раз возвращает все элементы i-ого цикла на свои места. Таким образом, первая повторившаяся перестановка будет единичной (I) и возникнет она когда все циклы прокрутятся на полные обороты. То есть, x должно быть минимальным положительным числом, делящимся на все n_i, то есть их НОК.

Таким образом, если найдётся перестановка с разбиением на циклы таким, что НОК их длин будет составлять x, она будет являться решением задачи. С другой стороны, по разбиению на циклы несложно сгенерировать и саму перестановку. Так, например, цикл длины m представляет собой перестановку вида 2, 3, …, m, 1. Итак, исходная задача эквивалентная следующей: необходимо разбить число n на слагаемые n_i, так чтобы их НОК был равен x.

Для решения получившейся задачи рассмотрим разложение числа x на простые множители. Поскольку НОК набора чисел представляет собой произведение всех простых множителей из этого набора, взятых со максимальными по всему набору степенями, справедливы следующие утверждения:

• числа n_i не должны содержать простых чисел, которых нет в разложении x;
• для каждого простого числа p, входящего в x со степенью alfa, должно найтись i, при котором n_i делится на p^alfa, но не должно найтись j при котором n_j делится на p^alfa  + 1.

Применим метод динамического программирования. Будем формировать числа n_i одно за другим. Рассмотрим k-ый шаг алгоритма. К этому моменту уже сформирован набор S_k = {n₁, n₂, …, n_k − 1} и на текущем шаге следует выбрать число n_k. При этом, вне зависимости от конкретного набора S_k текущее состояние может быть описано двумя числами: текущей частичной суммой n₁ + n₂ + …  + n_k − 1 и битовой маской, в которой для каждого простого числа p, входящего в разложение x со степенью alfa установлена единица тогда и только тогда, когда в наборе S_k имеется число, делящееся на p^alfa.

Оценим количество состояний. Первое число (текущая частичная сумма) не может превосходить n, в то время как максимальное число бит в битовой маске соответствует максимальному количеству различных простых делителей числа x и при ограничениях задачи не может превосходить 7. Итого, имеем не более (1000 + 1)2⁷ состояний. Для оптимизации количества переходов можно перебирать не все возможные n_k, а только делители числа x. При такой реализации решение с запасом укладывается и по времени, и по памяти.