让我们将长度 n 的排列定义为数组 p = [p1, p2, ..., pn],由 n 个从 1 到 n 范围内的不同整数组成。我们说这个排列将值 1 映射到值 p1,将值 2 映射到值 p2,依此类推。
Kyota Ootori 刚刚了解了排列的循环表示。循环是一个数字序列,该序列的每个元素都被映射到该序列的下一个元素(并且循环的最后一个元素被映射到循环的第一个元素)。循环表示是将 p 表示为形成 p 的循环的集合。例如,排列 p = [4, 1, 6, 2, 5, 3] 的循环表示类似于 (142)(36)(5),因为 1 被 4 替换,4 被 2 替换,2 被 1 替换,3 和 6 被交换,5 保持不变。
排列可能有多种循环表示,因此 Kyoya 定义排列的标准循环表示如下。首先,对每个循环内的元素重新排序,使最大的元素位于第一个。然后,对所有循环重新排序,以便它们按第一个元素排序。对于上面的示例,[4, 1, 6, 2, 5, 3] 的标准循环表示是 (421)(5)(63)。
现在,Kyoya 注意到,如果我们去掉标准循环表示中的括号,我们会得到另一种排列!例如,[4, 1, 6, 2, 5, 3] 将变为 [4, 2, 1, 5, 6, 3]。
Kyoya 注意到,在应用上述操作后,某些排列根本没有改变。他按照字典顺序将所有长度为 n 且不会改变的排列写在列表中。不幸的是,他的朋友 Tamaki Suoh 丢失了这份名单。 Kyoya 希望复制该列表,他需要你的帮助。给定整数 n 和 k,打印 Kyoya 列表中的第 k 个排列。
输入
第一行将包含两个整数 n, k (1 ≤ n ≤ 50, 1 ≤ k ≤ min{1018, l},其中 l 是 Kyoya 列表的长度)。
输出
打印 n 个空格分隔的整数,表示问题答案的排列。
示例
输入 #1
4 3
输出 #1
1 3 2 4
输入 #2
10 1
输出 #2
1 2 3 4 5 6 7 8 9 10
注意
标准循环表示为 (1)(32)(4),删除括号后给出了原始排列。列表中的第一个排列将是 [1, 2, 3, 4],而第二个排列将是 [1, 2, 4, 3]。