你遇到了一个大麻烦！你非常喜欢递推关系，甚至可能有点过度了。特别地，你是一个正线性递推关系（PLRR）的爱好者，其定义如下：首先，你选择关系的阶数 $k$。然后，你选择系数 $c_1, c_2, \dots, c_k$ 以及序列的前 $k$ 个元素 $a_1, a_2, \dots, a_k$。如果所有这些数字都是正整数，则该关系被称为“正”的。序列的其余部分随后可以使用以下公式无限生成：

$$a_{i+k} = c_1 \cdot a_i + c_2 \cdot a_{i+1} + \dots + c_k \cdot a_{i+k-1} \quad \text{对于 } i \ge 1$$

斐波那契数列是这种形式中最著名的递推关系，但还有许多其他的例子。

事实上，昨天在一阵疯狂的数学灵感中，你写下了所有可能的正线性递推关系的选择方式，以及每个关联的无限序列，并将它们记录在索引卡片上，每张卡片一个。（你有很多索引卡片；你是批量购买的。）这一切都有点模糊。但当你今天醒来时，你意识到你没有一个好的方法来排序或计数这些 PLRR。你尝试过仅仅按字典序对序列进行排序，但以“1”开头的序列太多了——你永远无法处理到后面的那些。

幸运的是，灵感再次降临！你意识到你可以改为仅根据序列的生成部分（即初始 $k$ 个值之后开始的序列部分）按字典序对 PLRR 进行排序。如果生成部分相同，则通过系数的字典序来打破平局。例如，$k=1, c_1=2, a_1=2$ 排在 $k=2, (c_1, c_2)=(2, 1), (a_1, a_2)=(1, 2)$ 之前，即使两者的序列延续部分是相同的。这使你能够正确地为你的卡片建立索引，从 1 开始，每张卡片都被分配一个编号。

给定卡片上的编号，请描述其上的序列！

输入格式

输入包含一行，为一个整数 $n$ ($1 \le n \le 10^9$)，即所需 PLRR 的索引。

输出格式

输出四行，详细说明所需的递推关系。第一行包含其阶数 $k$。第二行包含 $k$ 个系数 $c_1, \dots, c_k$。第三行包含 $k$ 个起始值 $a_1, \dots, a_k$。第四行包含生成值的前 10 个数字。

样例

样例输入 1

3

样例输出 1

2
1 1
1 1
2 3 5 8 13 21 34 55 89 144

样例输入 2

1235

样例输出 2

4
1 1 3 1
3 2 1 1
9 15 44 99 255 611 1519 3706 9129 22377