題目背景

小艾想要挑戰分治乘法。TA 將策略抽象成了如下問題：

現在給定一個目標集合 $T$，該集合是 $\{1,\dots,n\}$ 的一個子集（$1\leq n\leq 5\times 10^5$）。你需要透過一系列操作構造一些集合最後得到 $T$，具體來說有以下三種操作：

• 創造一個大小為一的集合 $|S|=1$。
• 將已經被構造出的兩個不交集合 $A, B$ 並起來，得到 $A\cup B$。
• 將已經被構造出的一個集合 $A$ 進行平移，也即 $A+x = \{ a+x : a\in A \}$。

一個已經被構造出的集合可以在之後被使用多次。同時你需要保證操作過程中出現的所有集合都是 $\{1,\dots,n\}$ 的子集。

你的代價是構造出的所有集合的大小之和，你不需要最小化代價，只需要讓代價控制不超過 $5\times 10^6$ 即可。你用的操作數量也不應超過 $10^6$。

輸入格式

從標準輸入讀入資料。

第一行輸入一個正整數 $n$。

接下來一行輸入一個 01 串，長度為 $n$，第 $x$ 位為 1 表示 $x\in T$，否則 $x\notin T$，保證 $T$ 非空。

輸出格式

輸出到標準輸出。

第一行輸出一個正整數 $m$ 表示你使用的操作數量。

接下來 $m$ 行，每行描述一個操作，設第 $i$ 次操作得到的集合為 $T_i$：

• 1 x 表示創造一個大小為一的集合 $\{x\}$。
• 2 x y 表示將不交集合 $T_x, T_y$ 並起來。
• 3 x y 表示將已經被構造出的一個集合進行平移，也即 $T_x+y$。

你需要保證所有操作滿足題目要求，並且最後一次操作產生的集合是 $T$。

範例

範例 1 輸入

5
11011

範例 1 輸出

5
1 1
1 4
2 1 2
3 3 1
2 3 4

說明

• 第一次操作：創造集合 $T_1=\{1\}$。
• 第二次操作：創造集合 $T_2=\{4\}$。
• 第三次操作：將 $T_1, T_2$ 並起來，得到 $T_3=\{1,4\}$。
• 第四次操作：將 $T_3$ 平移 $1$，得到 $T_4=\{2,5\}$。
• 第五次操作：將 $T_3, T_4$ 並起來，得到 $T_5=\{1,2,4,5\}$。這就得到了 $T$。

這個方案的總代價是 $1 + 1 + 2 + 2 + 4 = 10$。

提示

如果你的複雜度是好的，請相信常數。