AT_tkppc3_h 新入生歓迎数列 - Hard

[problemUrl]: https://atcoder.jp/contests/tkppc3/tasks/tkppc3_h 配点： $ 1000 $ 点 パ研の新入生の 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 $点 \] 追加の制約はない.