Problem Description

Xiao Ai wants to challenge divide-and-conquer multiplication. They abstract the strategy into the following problem:

You are 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 through a sequence of operations and finally obtain $T$. Specifically, there are three types of operations:

• Create a set of size one, $|S|=1$.
• Union two disjoint sets $A, B$ that have already been constructed, obtaining $A\cup B$.
• Translate (shift) a set $A$ that has already been constructed, i.e., $A+x = \{ a+x : a\in A \}$.

A constructed set can be used multiple times later. Meanwhile, you must ensure that all sets appearing during the process are subsets of $\{1,\dots,n\}$.

Your cost is the sum of the sizes of all constructed sets. You do not need to minimize the cost; you only need to keep the cost not exceeding $5\times 10^6$. The number of operations you use should also not exceed $10^6$.

Input Format

The first line contains a positive integer $n$.

The next line contains a 01 string of length $n$. The $x$-th character is 1 means $x\in T$, otherwise $x\notin T$. It is guaranteed that $T$ is non-empty.

Output Format

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

In the next $m$ lines, each line describes an operation. Let the set produced by the $i$-th operation be $T_i$:

• 1 x means creating a set of size one $\{x\}$.
• 2 x y means unioning the disjoint sets $T_x, T_y$.
• 3 x y means translating a constructed set, i.e., $T_x+y$.

You must ensure all operations satisfy the requirements, and the set produced by the last operation is exactly $T$.

5
11011

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

Hint

Sample #1 Explanation

• Operation 1: create the set $T_1=\{1\}$.
• Operation 2: create the set $T_2=\{4\}$.
• Operation 3: union $T_1, T_2$ to get $T_3=\{1,4\}$.
• Operation 4: translate $T_3$ by $1$ to get $T_4=\{2,5\}$.
• Operation 5: union $T_3, T_4$ to get $T_5=\{1,2,4,5\}$. This gives $T$.

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

Hint

If your complexity is good, please trust the constant factor.

Problem Usage Agreement

From the THUPC2024 (Tsinghua University Student Programming Contest and Intercollegiate Invitational Contest 2024) Preliminary.

The following “this repository” refers to the THUPC2024 Preliminary official repository (https://github.com/ckw20/thupc2024_pre_public).

1. Any organization or individual may use or repost the problems in this repository for free.

2. Any organization or individual, when using the problems in this repository, should make them free of charge and publicly accessible. It is strictly forbidden to profit from these problems or to add special permissions to these problems.

3. If conditions allow, when using the problems in this repository, please also provide ways to obtain resources such as testdata, reference solutions, and editorials. Otherwise, please attach the GitHub address of this repository.

Translated by ChatGPT 5