Johnny 写了一个将排列转换为二叉搜索树（BST）的转换器：给定一个排列 $(\pi_1, \pi_2, \dots, \pi_n)$，它将 $\pi_1$ 分配给 BST 的根节点；对于 $(\pi_2, \pi_3, \dots, \pi_n)$ 中比 $\pi_1$ 小的数（保持它们在原排列中的相对顺序！），它递归地创建一棵 BST 并将其作为根节点的左子树；对称地，对于 $(\pi_2, \pi_3, \dots, \pi_n)$ 中比 $\pi_1$ 大的数，它也递归地创建一棵 BST 并将其作为根节点的右子树。

让 Johnny 感到惊讶的是，不同的排列可能会生成相同的 BST——例如，排列 $(2, 3, 1)$ 和 $(2, 1, 3)$ 会生成相同的 BST。他觉得这个事实非常神奇，并立即定义了“Johnny 数” $J_k$：第 $k$ 个 Johnny 数 $J_k$ 是最小的 $n$，使得存在一棵含有 $n$ 个节点（标记为 $1, 2, \dots, n$）的 BST，该树可以由恰好 $k$ 个不同的 $1, 2, \dots, n$ 的排列生成。

对 Johnny 数的研究非常困难，而且它们的热度正在下降。请帮助 Johnny 计算给定 $k$ 的 Johnny 数 $J_k$。

输入格式

输入的第一行包含一个自然数 $k$（$1 \le k \le 10^{11}$）。

输出格式

在输出的第一行中，打印一个正整数：第 $k$ 个 Johnny 数 $J_k$（假设它存在且不超过 $5\,000$）。 输出的第二行必须包含 $J_k$ 个整数——在生成该 BST 的 $k$ 个排列中，字典序最小的那个排列。

否则，即如果 $J_k$ 不存在或大于 $5\,000$，你应该输出单词 “NIE”（波兰语中的“否”）。

样例

输入样例 1

8

输出样例 1

5
2 1 4 3 5

说明

拥有恰好 8 个生成排列的树如下图所示：

所有生成该树的排列为：$(2, 1, 4, 3, 5)$，$(2, 1, 4, 5, 3)$，$(2, 4, 1, 3, 5)$，$(2, 4, 1, 5, 3)$，$(2, 4, 3, 1, 5)$，$(2, 4, 3, 5, 1)$，$(2, 4, 5, 1, 3)$，$(2, 4, 5, 3, 1)$。