Задача . E. Новогодние перестановки

Да, мы не смогли придумать новогоднюю легенду для этой задачи.

Перестановка длины \(n\) — это массив \(n\) целых чисел, таких что каждое целое число от \(1\) до \(n\) появляется в нем ровно один раз.

Элемент \(y\) перестановки \(p\) достижим из элемента \(x\), Если \(x = y\), или \(p_x = y\), или \(p_{p_x} = y\) и так далее.

Определим декомпозицию перестановки \(p\) следующим образом: сначала у нас есть перестановка \(p\), все элементы которой не помечены, и пустой список \(l\). Затем мы делаем следующее: пока хотя бы один элемент не помечен в \(p\), находим самый левый такой элемент, перечисляем все элементы, которые достижимы из него в порядке их появления в \(p\), помечаем все эти элементы, затем циклически сдвигаем список этих элементов так, чтобы максимум появился в первой позиции, и добавляем этот список как элемент в \(l\). После того, как все элементы помечены, \(l\) является результатом этой декомпозиции.

Например, если мы хотим построить декомпозицию \(p = [5, 4, 2, 3, 1, 7, 8, 6]\), мы делаем следующее:

1. изначально \(p = [5, 4, 2, 3, 1, 7, 8, 6]\) (жирным шрифтом выделены помеченные элементы), \(l = []\);
2. самый левый не помеченный элемент — \(5\); \(5\) и \(1\) достижимы из него, поэтому список, который мы хотим сдвинуть, — \([5, 1]\); нет необходимости сдвигать его, так как максимум уже является первым элементом;
3. \(p = [\textbf{5}, 4, 2, 3, \textbf{1}, 7, 8, 6]\), \(l = [[5, 1]]\);
4. самый левый не помеченный элемент — \(4\), список достижимых элементов из него — это \([4, 2, 3]\); максимум уже первый элемент, поэтому сдвигать его не нужно;
5. \(p = [\textbf{5}, \textbf{4}, \textbf{2}, \textbf{3}, \textbf{1}, 7, 8, 6]\), \(l = [[5, 1], [4, 2, 3]]\);
6. самый левый не помеченный элемент — \(7\), список достижимых элементов из него — это \([7, 8, 6]\); мы должны сдвинуть его, чтобы он стал \([8, 6, 7]\);
7. \(p = [\textbf{5}, \textbf{4}, \textbf{2}, \textbf{3}, \textbf{1}, \textbf{7}, \textbf{8}, \textbf{6}]\), \(l = [[5, 1], [4, 2, 3], [8, 6, 7]]\);
8. все элементы помечены, так что \([[5, 1], [4, 2, 3], [8, 6, 7]]\) — результат декомпозиции.

Определим новогоднее преобразование перестановки следующим образом: построим декомпозицию этой перестановки; затем отсортируем все списки в декомпозиции по возрастанию первых элементов (мы не меняем местами элементы в этих списках, только сами списки); затем объединим списки в один список, который становится новой перестановкой. Например, новогоднее преобразование \(p = [5, 4, 2, 3, 1, 7, 8, 6]\) строится следующим образом:

1. декомпозиция равна \([[5, 1], [4, 2, 3], [8, 6, 7]]\);
2. после сортировки, декомпозиция становится равна \([[4, 2, 3], [5, 1], [8, 6, 7]]\);
3. \([4, 2, 3, 5, 1, 8, 6, 7]\) — результат преобразования.

Назовем перестановку хорошей, если результат ее преобразования совпадает с самой перестановкой. Например, \([4, 3, 1, 2, 8, 5, 6, 7]\) это хорошая перестановка; а \([5, 4, 2, 3, 1, 7, 8, 6]\) плохая, так как результатом преобразования является \([4, 2, 3, 5, 1, 8, 6, 7]\).

Ваша задача состоит в следующем: при заданных \(n\) и \(k\) найти \(k\)-ю (лексикографически) хорошую перестановку длины \(n\).