小艾想要挑战分治乘法。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。

Ai wants to take on the challenge of partition multiplication. Ai abstracts the strategy to the following problem:

Now given a target set T which is a subset of {1,\dots,n} (1\leq n\leq 5\times 10^5). You need to construct some sets to finally get T through a series of operations, specifically the following three operations:

• Create a set of size one |S|=1.
• Concatenate two disjoint sets A, B that have already been constructed to get A\cup B.
• Translate an already constructed set A, i.e. A+x = { a+x : a\in A }.

A set that has already been constructed can be used many times later. At the same time you need to ensure that all sets that appear during the operation are subsets of {1,\dots,n}.

The cost is the sum of the sizes of all the sets constructed, and you don't need to minimize the cost, just keep it to no more than 5\times 10^6. You should not use more than 10^6 operations.

第一行输入一个正整数 n。

接下来一行输入一个 01 串，长度为 n，第 x 位为 1 表示 x\in T，否则 x\notin T，保证 T 非空。

The first line inputs a positive integer n.

The next line inputs a 01 string of length n, with the x-th bit being 1 to indicate x\in T, otherwise x\notin T. It's guaranteed that T is not null.

第一行输出一个正整数 m 表示你使用的操作数量。

接下来 m 行，每行描述一个操作，设第 i 次操作得到的集合为 T_i：

• 1 x 表示创造一个大小为一的集合 {x}。
• 2 x y 表示将不交集合 T_x, T_y 并起来。
• 3 x y 表示将已经被构造出的一个集合进行平移，也即 T_x+y。

你需要保证所有操作满足题目要求，并且最后一次操作产生的集合是 T。

The first line outputs a positive integer m indicating the number of operations you used.

The next m lines, each describing one operation, let the set obtained by the ith operation be T_i:

• 1 x denotes the creation of a set {x} of size one.
• 2 x y denotes the concatenation of disjoint sets T_x, T_y.
• 3 x y means to translate a set that has already been constructed, i.e. T_x+y.

You need to make sure that all operations satisfy the requirements of the topic and that the last operation produces a set T.

• 第一次操作：创造集合 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。

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

• First operation: create the set T_1={1}.
• Second operation: create the set T_2={4}.
• Third operation: combine T_1, T_2 to get T_3={1,4}. Fourth operation: create the set T_3.
• Fourth operation: translate T_3 by 1 to get T_4={2,5}.
• Fifth operation: combine T_3, T_4 to get T_5={1,2,4,5}. This gives T.

The total cost of this program is 1 + 1 + 2 + 2 + 4 = 10.

If your time complexity is good, trust the time constant.