実行時間制限: 3 sec / メモリ制限: 256 MB
問題文
パ研の新入生の PAKEN 君は, 長さ N の数列 P = {P_1, P_2, P_3, ..., P_N} を E869120 からもらった. 最初 P のすべての要素は 0 である.
PAKEN 君は, 数列 P に以下の操作を好きな順番で, 合計で 550 \ 000 回以内行うことによって, この数列を A = {A_1, A_2, A_3, ..., A_N} と同じにしようと思った.
- 操作 1: 1 以上 N 以下の整数 x を選び, P_x の値を 1 に変更する.
- 操作 2: 1 以上 N 以下の整数 y, z を選び, P_y の値に P_z の値を足す. ただし, y = z であってもよい. また, P_y の値は 10^{18} を超えてはならない.
PAKEN 君はまだ幼いので, どのような手順で操作をすればよいのか分からない. 彼を助けるために, あなたは操作の手順の一例を示さなければならない.
入力
入力は, 以下の形式で標準入力から与えられる.
N A_1 A_2 A_3 ... A_N
出力
出力は, 以下の形式で標準出力から行うこと.
Q (1 回目の操作の情報) (2 回目の操作の情報) (3 回目の操作の情報) ... (Q 回目の操作の情報)
まず最初に, 行う操作の回数 Q を出力しなければならない. Q は 0 以上 550 \ 000 以下の整数でなければならない. 次の Q 行, 各回の操作の情報は, 以下のように出力しなければならない.
(☆) 操作 1 を行う場合
1 x
これは, P_x を 1 にするという操作を行う, という意味である.
(★) 操作 2 を行う場合
2 y z
これは, P_y に P_z の値を足すという操作を行う, という意味である.
制約
- N は 2 以上 200 \ 000 以下の整数である.
- A_1 = 1 を満たす.
- A_i (1 \leq i \leq N) は 1 以上 2^{30} - 1 以下の整数である.
小課題
小課題1 [ 60点 ]
- N = 2 を満たす.
小課題2 [ 140点 ]
- N \leq 8 \ 000 を満たす.
小課題3 [ 80点 ]
- N \leq 16 \ 000 を満たす.
小課題4 [ 230点 ]
- N \leq 25 \ 000 を満たす.
小課題5 [ 270点 ]
- N \leq 160 \ 000 を満たす.
小課題6 [ 220点 ]
- 追加の制約はない.
入力例1
2 1 4
出力例1
4 1 1 1 2 2 2 2 2 2 2
操作によって, 数列の値は {0, 0} -> {1, 0} -> {1, 1} -> {1, 2} -> {1, 4} というように変わる.
入力例2
3 1 3 5
出力例2
8 1 1 2 1 1 2 3 1 1 1 2 1 2 2 2 1 2 3 1 1 1
操作によって, 数列の値は {0, 0, 0} -> {1, 0, 0} -> {2, 0, 0} -> {2, 0, 2} -> {1, 0, 2} -> {3, 0, 2} -> {3, 3, 2} -> {3, 3, 5} -> {1, 3, 5} というように変わる.
writer: E869120