簡単な問題文

謎のモノイド (M, \oplus) と、これを計算する CPU が 4 個あります。

整数 N が与えられるので、M の列 A = (A_1, A_2, …, A_N) から A の累積 \oplus を 4 並列で計算してください。
その際、操作回数を最小化してください。

厳密な問題文

整数 N が与えられます。以下の (独自言語の) プログラムを作成してください。その際、命令数を最小化してください。

プログラムの仕様

このプログラムでは、2004 個の変数 A[1], A[2], …, A[2000], C_1, C_2, C_3, C_4 を扱うことができる。各変数は整数列を 1 つ持つことができ、A[i] (1 ≤ i ≤ 2000) の初期値は A[i] = (i) である。
( (i) は i のみからなる整数列を表す。)

プログラムの実行終了時点で、以下の条件が満たされなければならない。

• i = 1, 2, …, N のそれぞれについて、A[i] = (1, 2, …, i) である。

プログラムの形式

プログラムの 1 行目にはプログラムの命令数を表す整数 L が書かれる。
プログラムの 2 行目から 4L+1 行目には L 個の命令が 4 行ずつ書かれる。命令は上から下に順次実行される。

命令は 12 個の整数 c_1, a_1, b_1, c_2, a_2, b_2, c_3, a_3, b_3, c_4, a_4, b_4で書かれる。各整数は 1 以上 2000 以下でなければならない。
各命令では以下の操作を順に行う。

1. C_1 に \text{concat}(A[a_1], A[b_1]) を代入する。
2. C_2 に \text{concat}(A[a_2], A[b_2]) を代入する。
3. C_3 に \text{concat}(A[a_3], A[b_3]) を代入する。
4. C_4 に \text{concat}(A[a_4], A[b_4]) を代入する。
5. A[c_1] に C_1 を代入する。
6. A[c_2] に C_2 を代入する。
7. A[c_3] に C_3 を代入する。
8. A[c_4] に C_4 を代入する。

ここで、\text{concat}(x, y) とは、整数列 x, y をこの順で連結した整数列を表す。

制約

• N は整数
• 2 ≤ N ≤ 10^3

部分点

• 2 ≤ N ≤ 16 を満たすデータセットに正解した場合は 200 点が与えられる。
• 17 ≤ N ≤ 10^3 を満たすデータセットに正解した場合は 300 点が与えられる。

入力例 1

2

出力例 1

1
2 1 2
2000 2000 2000
2000 2000 2000
2000 2000 2000

1 回目の命令で、A[2] は (1, 2) に、A[2000] は (2000, 2000) に変化します。

実行終了時点で A[1] = (1), A[2] = (1, 2) となっているので、これは仕様を満たすプログラムです。

入力例 2

4

出力例 2

2
2 1 2
4 3 4
2000 2000 2000
2000 2000 2000
3 2 3
4 2 4
2000 2000 2000
2000 2000 2000

1 回目の命令で、A[2] は (1, 2) に、A[4] は (3, 4) に、A[2000] は (2000, 2000) に変化します。
2 回目の命令で、A[3] は (1, 2, 3) に、A[4] は (1, 2, 3, 4) に、A[2000] は (2000, 2000, 2000, 2000) に変化します。

実行終了時点で A[1] = (1), A[2] = (1, 2), A[3] = (1, 2, 3), A[4] = (1, 2, 3, 4) となっているので、これは仕様を満たすプログラムです。