2. Fibonacci Partitioning
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Fibonacci sequence begins with the numbers $$$F_1=1$$$ and $$$F_2=1$$$. Each subsequent number is the sum of the two preceding ones. The indexing starts at one.

You are to construct a sequence of $$$n$$$ numbers that includes one "restart" after position $$$i$$$: that is, the first $$$i$$$ Fibonacci numbers ($$$2 \leq i \leq n - 2$$$) are written down, after which the sequence begins anew from $$$F_1$$$ and $$$F_2$$$ and continues following the same rule until there are exactly $$$n$$$ numbers in the sequence.

Choose the value of $$$i$$$ such that the sum of all $$$n$$$ numbers is minimized. If multiple positions yield the same sum, choose the smallest $$$i$$$.

Input

A single integer $$$n$$$ ($$$6 \le n \le 80$$$).

Output

On the first line, output the chosen position $$$i$$$. On the second line, output the $$$n$$$ numbers of the resulting sequence, separated by spaces.

Scoring

Each passed test yields an equal number of points; a complete solution receives 100 points.

Examples
Input
6
Output
3
1 1 2 1 1 2
Input
7
Output
3
1 1 2 1 1 2 3
Note

Note that the answer may exceed the maximum value of a 32-bit integer variable; therefore, you must use a 64-bit integer data type (the 'int64' type in Pascal, 'long long' in C++, and 'long' in Java and C#). In Python, no additional steps are required.