题目描述

小艾想要挑战分治乘法。TA 将策略抽象成了如下问题：

现在给定一个目标集合 $T$，该集合是 $\{1,\dots,n\}$ 的一个子集（$1\leq n\leq 5\times 10^5$）。
你需要通过一系列操作构造一些集合最后得到 $T$，具体来说有以下三种操作：

1. 创造一个大小为一的集合 $|S|=1$。
2. 将已经被构造出的两个不交集合 $A, B$ 并起来，得到 $A\cup B$。
3. 将已经被构造出的一个集合 $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$。

样例

输入

5
11011

输出

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$。

提示

如果你的复杂度是好的，请相信常数。