CF553B.Kyoya and Permutation

Let's define the permutation of length n as an array p = [_p_1, _p_2, ..., p__n] consisting of n distinct integers from range from 1 to n. We say that this permutation maps value 1 into the value _p_1, value 2 into the value _p_2 and so on.

Kyota Ootori has just learned about cyclic representation of a permutation. A cycle is a sequence of numbers such that each element of this sequence is being mapped into the next element of this sequence (and the last element of the cycle is being mapped into the first element of the cycle). The cyclic representation is a representation of p as a collection of cycles forming p. For example, permutation p = [4, 1, 6, 2, 5, 3] has a cyclic representation that looks like (142)(36)(5) because 1 is replaced by 4, 4 is replaced by 2, 2 is replaced by 1, 3 and 6 are swapped, and 5 remains in place.

Permutation may have several cyclic representations, so Kyoya defines the standard cyclic representation of a permutation as follows. First, reorder the elements within each cycle so the largest element is first. Then, reorder all of the cycles so they are sorted by their first element. For our example above, the standard cyclic representation of [4, 1, 6, 2, 5, 3] is (421)(5)(63).

Now, Kyoya notices that if we drop the parenthesis in the standard cyclic representation, we get another permutation! For instance, [4, 1, 6, 2, 5, 3] will become [4, 2, 1, 5, 6, 3].

Kyoya notices that some permutations don't change after applying operation described above at all. He wrote all permutations of length n that do not change in a list in lexicographic order. Unfortunately, his friend Tamaki Suoh lost this list. Kyoya wishes to reproduce the list and he needs your help. Given the integers n and k, print the permutation that was k-th on Kyoya's list.

我们定义长度为 $n$ 的排列为一个数组 $p = [p_1, p_2, \dots, p_n]$，其中包含 $1$ 到 $n$ 范围内互不相同的 $n$ 个整数。我们称该排列将数值 $1$ 映射为 $p_1$，将数值 $2$ 映射为 $p_2$，依此类推。

京谷大鸟（Kyota Ootori）刚刚学习了排列的循环表示法。一个循环是一个数字序列，其中该序列中每个元素被映射为序列中的下一个元素（而循环的最后一个元素被映射为循环的第一个元素）。循环表示法是将排列 $p$ 表示为若干个构成 $p$ 的不相交循环的集合。例如，排列 $p = [4, 1, 6, 2, 5, 3]$ 的循环表示为 $(142)(36)(5)$，因为 $1$ 被映射为 $4$，$4$ 被映射为 $2$，$2$ 被映射为 $1$；$3$ 和 $6$ 相互交换；而 $5$ 映射到自身（即保持不动）。

一个排列可能有多种循环表示形式，因此京谷定义其标准循环表示法如下：

1. 对每个循环内部的元素重新排序，使得最大元素排在最前面；
2. 再对所有循环整体重新排序，使得这些循环按各自首元素升序排列。

以上述例子 $[4, 1, 6, 2, 5, 3]$ 为例，其标准循环表示为 $(421)(5)(63)$。

现在，京谷注意到：若将标准循环表示法中的括号全部去掉，便得到另一个排列！例如，$[4, 1, 6, 2, 5, 3]$ 经此操作后变为 $[4, 2, 1, 5, 6, 3]$。

京谷进一步发现，某些排列在执行上述操作后完全不变。他将所有长度为 $n$ 的、满足该性质的排列按字典序列成一张表。不幸的是，他的朋友须王环（Tamaki Suoh）弄丢了这张表。京谷希望重现该表，因此需要你的帮助。给定整数 $n$ 和 $k$，请输出该表中第 $k$ 个排列。

The first line will contain two integers n, k (1 ≤ n ≤ 50, 1 ≤ k ≤ min{1018, l} where l is the length of the Kyoya's list).

第一行包含两个整数 $n$、$k$（$1 ≤ n ≤ 50$，$1 ≤ k ≤ \min\{10^{18},\,l\}$，其中 $l$ 是京也列表的长度）。

Print n space-separated integers, representing the permutation that is the answer for the question.

输出 n 个空格分隔的整数，表示该问题的答案所对应的排列。

The standard cycle representation is (1)(32)(4), which after removing parenthesis gives us the original permutation. The first permutation on the list would be [1, 2, 3, 4], while the second permutation would be [1, 2, 4, 3].

标准的轮换表示法为 $(1)(32)(4)$，去掉括号后即得到原始排列。列表中的第一个排列是 $[1,\,2,\,3,\,4]$，而第二个排列是 $[1,\,2,\,4,\,3]$。