問題背景
小艾（Xiao Ai）は分割統治法を用いた乗算に挑戦したいと考えています。彼女は戦略を次のような問題として抽象化しました。
目標集合 $T$ が与えられます。これは $\{1, \dots, n\}$ の部分集合です（$1 \leq n \leq 5 \times 10^5$）。一連の操作を通じていくつかの集合を構築し、最終的に $T$ を得る必要があります。具体的には、以下の3種類の操作が可能です。
- サイズが1の集合 $|S|=1$ を作成する。
- すでに構築された2つの互いに素な集合 $A, B$ を合併し、$A \cup B$ を得る。
- すでに構築された集合 $A$ を平行移動する。すなわち、$A+x = \{ a+x : a \in A \}$ を得る。
一度構築された集合は、その後何度でも使用できます。また、操作の過程で現れるすべての集合が $\{1, \dots, n\}$ の部分集合であることを保証しなければなりません。
あなたのコストは、構築されたすべての集合のサイズの総和です。コストを最小化する必要はありませんが、コストを $5 \times 10^6$ 以下に抑える必要があります。また、使用する操作の回数も $10^6$ を超えてはなりません。
入力
標準入力からデータが与えられます。
1行目に正整数 $n$ が与えられます。
2行目に長さ $n$ の 01 文字列が与えられます。$x$ 番目の文字が 1 ならば $x \in T$ であり、そうでなければ $x \notin T$ です。$T$ は空集合ではないことが保証されます。
出力
標準出力へ出力してください。
1行目に、使用した操作の回数 $m$ を出力してください。
続く $m$ 行に、各操作を記述してください。$i$ 番目の操作で得られる集合を $T_i$ とします。
1 x：サイズ1の集合 $\{x\}$ を作成する。2 x y：互いに素な集合 $T_x, T_y$ を合併する。3 x y：すでに構築された集合 $T_x$ を $y$ だけ平行移動する。すなわち $T_x+y$ を得る。
すべての操作が問題の要求を満たし、かつ最後の操作で生成される集合が $T$ であることを保証してください。
入出力例
入出力例 1
5 11011
5 1 1 1 4 2 1 2 3 3 1 2 3 4
注記
- 1回目の操作：集合 $T_1=\{1\}$ を作成する。
- 2回目の操作：集合 $T_2=\{4\}$ を作成する。
- 3回目の操作：$T_1, T_2$ を合併し、$T_3=\{1,4\}$ を得る。
- 4回目の操作：$T_3$ を $1$ だけ平行移動し、$T_4=\{2,5\}$ を得る。
- 5回目の操作：$T_3, T_4$ を合併し、$T_5=\{1,2,4,5\}$ を得る。これで $T$ が得られた。
この手法の総コストは $1 + 1 + 2 + 2 + 4 = 10$ です。
ヒント
計算量が適切であれば、定数倍を信じてください。