CF1279E.New Year Permutations

Yeah, we failed to make up a New Year legend for this problem.

A permutation of length $n$ is an array of $n$ integers such that every integer from $1$ to $n$ appears in it exactly once.

An element $y$ of permutation $p$ is reachable from element $x$ if $x = y$, or $p_x = y$, or $p_{p_x} = y$, and so on.

The decomposition of a permutation $p$ is defined as follows: firstly, we have a permutation $p$, all elements of which are not marked, and an empty list $l$. Then we do the following: while there is at least one not marked element in $p$, we find the leftmost such element, list all elements that are reachable from it in the order they appear in $p$, mark all of these elements, then cyclically shift the list of those elements so that the maximum appears at the first position, and add this list as an element of $l$. After all elements are marked, $l$ is the result of this decomposition.

For example, if we want to build a decomposition of $p = [5, 4, 2, 3, 1, 7, 8, 6]$, we do the following:

1. initially $p = [5, 4, 2, 3, 1, 7, 8, 6]$ (bold elements are marked), $l = []$;
2. the leftmost unmarked element is $5$; $5$ and $1$ are reachable from it, so the list we want to shift is $[5, 1]$; there is no need to shift it, since maximum is already the first element;
3. $p = [\textbf{5}, 4, 2, 3, \textbf{1}, 7, 8, 6]$, $l = [[5, 1]]$;
4. the leftmost unmarked element is $4$, the list of reachable elements is $[4, 2, 3]$; the maximum is already the first element, so there's no need to shift it;
5. $p = [\textbf{5}, \textbf{4}, \textbf{2}, \textbf{3}, \textbf{1}, 7, 8, 6]$, $l = [[5, 1], [4, 2, 3]]$;
6. the leftmost unmarked element is $7$, the list of reachable elements is $[7, 8, 6]$; we have to shift it, so it becomes $[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. all elements are marked, so $[[5, 1], [4, 2, 3], [8, 6, 7]]$ is the result.

The New Year transformation of a permutation is defined as follows: we build the decomposition of this permutation; then we sort all lists in decomposition in ascending order of the first elements (we don't swap the elements in these lists, only the lists themselves); then we concatenate the lists into one list which becomes a new permutation. For example, the New Year transformation of $p = [5, 4, 2, 3, 1, 7, 8, 6]$ is built as follows:

1. the decomposition is $[[5, 1], [4, 2, 3], [8, 6, 7]]$;
2. after sorting the decomposition, it becomes $[[4, 2, 3], [5, 1], [8, 6, 7]]$;
3. $[4, 2, 3, 5, 1, 8, 6, 7]$ is the result of the transformation.

We call a permutation good if the result of its transformation is the same as the permutation itself. For example, $[4, 3, 1, 2, 8, 5, 6, 7]$ is a good permutation; and $[5, 4, 2, 3, 1, 7, 8, 6]$ is bad, since the result of transformation is $[4, 2, 3, 5, 1, 8, 6, 7]$.

Your task is the following: given $n$ and $k$, find the $k$-th (lexicographically) good permutation of length $n$.

是的，我们没能为本题编出一个新年传说。

长度为 $n$ 的排列（permutation）是一个由 $n$ 个整数组成的数组，其中每个从 $1$ 到 $n$ 的整数恰好出现一次。

在排列 $p$ 中，元素 $y$ 被称为可从元素 $x$ 到达（reachable from $x$），当且仅当满足以下条件之一：$x = y$，或 $p_x = y$，或 $p_{p_x} = y$，依此类推。

排列 $p$ 的分解（decomposition）定义如下：初始时，我们有一个未标记任何元素的排列 $p$，以及一个空列表 $l$。然后重复执行以下操作：只要 $p$ 中还存在至少一个未被标记的元素，我们就找出最左侧的未标记元素；列出所有可从该元素到达的元素（按它们在 $p$ 中出现的顺序）；将这些元素全部标记；接着对这个元素列表进行循环移位（cyclically shift），使得其中最大值位于首位；最后将该移位后的列表作为一个元素加入 $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$ 到达的元素是 $5$ 和 $1$，因此待移位列表为 $[5, 1]$；由于最大值 $5$ 已在首位，无需移位；
3. $p = [\textbf{5}, 4, 2, 3, \textbf{1}, 7, 8, 6]$，$l = [[5, 1]]$；
4. 最左侧未标记元素为 $4$，可到达元素为 $[4, 2, 3]$；最大值 $4$ 已在首位，无需移位；
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]]$。

一个排列的新年变换（New Year transformation）定义如下：首先计算该排列的分解；然后将分解所得的所有列表，按其首元素升序排序（注意：不改变各列表内部元素顺序，仅调整列表之间的顺序）；最后将这些列表连接（concatenate）成一个单一列表，即得到新的排列。例如，对 $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]$，即为变换结果。

若一个排列经新年变换后仍等于自身，则称其为好排列（good permutation）。例如，$[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$，求长度为 $n$ 的所有好排列中，字典序第 $k$ 小的那个排列。

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

Then the test cases follow. Each test case is represented by one line containing two integers $n$ and $k$ ($1 \le n \le 50$, $1 \le k \le 10^{18}$).

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 表示测试用例的数量。

接下来是各测试用例。每个测试用例由一行组成，包含两个整数 $n$ 和 $k$（$1 \le n \le 50$，$1 \le k \le 10^{18}$）。

For each test case, print the answer to it as follows: if the number of good permutations of length $n$ is less than $k$, print one integer $-1$; otherwise, print the $k$-th good permutation on $n$ elements (in lexicographical order).

对于每个测试用例，按如下方式输出其答案：如果长度为 $n$ 的好排列的个数小于 $k$，则输出一个整数 $-1$；否则，输出 $n$ 个元素构成的第 $k$ 个好排列（按字典序）。