C - Calculator Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

すぬけくんは整数 x,y を持っています． 最初 x=0,y=0 です．

すぬけくんは，以下の 4 つの操作を好きな順で好きな回数行なえます．

  • 操作 1: x の値を x+1 で置き換える

  • 操作 2: y の値を y+1 で置き換える

  • 操作 3: x の値を x+y で置き換える

  • 操作 4: y の値を x+y で置き換える

正整数 N が与えられます．

130 回以内の操作で，x の値を N にしてください． このとき，y にはどんな値が入っていても構いません． この問題の制約下で，このような操作列が存在することは証明できます．

制約

  • 1 \leq N \leq 10^{18}
  • 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

N

出力

以下の形式で答えを出力せよ．

K
t_1
t_2
\vdots
t_K

ここで，K (0 \leq K \leq 130) は操作回数を表し，t_i (1 \leq t_i \leq 4)は i 番目に行う操作を表す整数である．

入力例 1

4

出力例 1

5
1
4
2
3
1

(x,y) の値は， (0,0)\rightarrow (操作 1) \rightarrow (1,0) \rightarrow (操作 4) \rightarrow (1,1) \rightarrow (操作 2) \rightarrow (1,2) \rightarrow (操作 3) \rightarrow (3,2) \rightarrow (操作 1) \rightarrow (4,2) と変化し，最終的な x の値は N に一致しています．

Score : 600 points

Problem Statement

Snuke has integers x and y. Initially, x=0,y=0.

Snuke can do the following four operations any number of times in any order:

  • Operation 1: Replace the value of x with x+1.

  • Operation 2: Replace the value of y with y+1.

  • Operation 3: Replace the value of x with x+y.

  • Operation 4: Replace the value of y with x+y.

You are given a positive integer N. Do at most 130 operations so that x will have the value N. Here, y can have any value. We can prove that such a sequence of operations exists under the constraints of this problem.

Constraints

  • 1 \leq N \leq 10^{18}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N

Output

Print your answer in the following format:

K
t_1
t_2
\vdots
t_K

Here, K (0 \leq K \leq 130) denotes the number of operations, and t_i(1 \leq t_i \leq 4) represents the i-th operation to be done.

Sample Input 1

4

Sample Output 1

5
1
4
2
3
1

Here, the values of x and y change as follows: (0,0)\rightarrow (Operation 1) \rightarrow (1,0) \rightarrow (Operation 4) \rightarrow (1,1) \rightarrow (Operation 2) \rightarrow (1,2) \rightarrow (Operation 3) \rightarrow (3,2) \rightarrow (Operation 1) \rightarrow (4,2), and the final value of x matches N.