Seiji Maki не только любит наблюдать за развитием отношений, он также любит наблюдать за последовательностями чисел, особенно перестановками. Сегодня он смотрит на почти отсортированные перестановки.
Перестановка \(a_1, a_2, \dots, a_n\) чисел \(1, 2, \dots, n\) считается почти отсортированной, если условие \(a_{i + 1} \ge a_i - 1\) выполняется для всех \(i\) от \(1\) до \(n - 1\) включительно.
Maki рассматривает список всех почти отсортированных перестановок чисел \(1, 2, \dots, n\), приведенных в лексикографическом порядке, и хочет найти в этом списке перестановку \(k\)-ю. Можете ли вы помочь ему найти такую перестановку?
Перестановка \(p\) лексикографически меньше перестановки \(q\), если и только если выполняется следующее:
- в первой позиции, где \(p\) и \(q\) различны, в перестановке \(p\) элемент меньше, чем соответствующий элемент в \(q\).
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую \(k\)-ю почти отсортированную перестановку длины \(n\) в лексикографическом порядке, или \(-1\), если ее не существует.
Примечание
Для первого и второго набора входных данных список почти отсортированных перестановок с \(n = 1\) составляет \(\{[1]\}\).
Для третьего и пятого набора входных данных список почти отсортированных перестановок с \(n = 3\) составляет \(\{[1, 2, 3], [1, 3, 2], [2, 1, 3], [3, 2, 1]\}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 1
1 2
3 3
6 5
3 4
|
1
-1
2 1 3
1 2 4 3 5 6
3 2 1
|