Background

Special for beginners, ^_^

Description

如果一个整数序列 $a_1,a_2,\dots,a_n$ 的每个数字都在 1 到 n 之间，且没有两个数字相等，则称这个序列为全排列。例如 1,3,2 以及 4,3,2,1 都是全排列。

我们将所有的全排列排序，定义全排列 $a_1,a_2,\dots,a_n$ 与 $b_1,b_2,\dots,b_m$ 的排序先后关系如下：

如果 n<m，则 a 序列更靠前 如果 n>m，则 b 序列更靠前 如果 n=m，则以字典序规则比较 a 序列与 b 序列，字典序更小的序列更靠前。 根据上述定义，可以得到：

第 1 个全排列是 1

第 2 个全排列是 1 2

第 3 个全排列是 2 1

第 4 个全排列是 1 2 3

给定 k，请输出第 k 个全排列。

Format

Input

每（$\le10^5$）行一个整数：表示 k（$\le10^{19}$）。

Output

每行输出第 k 个全排列。

Samples

5

1 3 2

Limitation

1s, 1024KiB for each test case.