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

Перестановка длины $$$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$$$.