Xiao Ai wants to challenge herself with divide-and-conquer multiplication. She has abstracted her strategy into the following problem:

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 $T$ through a series of operations. Specifically, there are three types of operations:

• Create a set of size one: $|S|=1$.
• Union two disjoint sets $A$ and $B$ that have already been constructed to obtain $A \cup B$.
• Translate a set $A$ that has already been constructed: $A+x = \{ a+x : a\in A \}$.

A set that has already been constructed can be used multiple times later. You must ensure that all sets appearing during the operations 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 ensure the total cost does not exceed $5 \times 10^6$. The number of operations you use should not exceed $10^6$.

Input

Read from standard input.

The first line contains a positive integer $n$.

The next line contains a binary string of length $n$. The $x$-th character is 1 if $x \in T$, and 0 otherwise. It is guaranteed that $T$ is non-empty.

Output

Write to standard output.

The first line contains a positive integer $m$, representing the number of operations you use.

The next $m$ lines each describe an operation. Let $T_i$ be the set obtained by the $i$-th operation:

• 1 x means to create a set of size one $\{x\}$.
• 2 x y means to union the disjoint sets $T_x$ and $T_y$.
• 3 x y means to translate a previously constructed set $T_x$ by $y$, i.e., $T_x+y$.

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

Examples

Input 1

5
11011

Output 1

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

Note 1

• First operation: Create set $T_1=\{1\}$.
• Second operation: Create set $T_2=\{4\}$.
• Third operation: Union $T_1$ and $T_2$ to get $T_3=\{1,4\}$.
• Fourth operation: Translate $T_3$ by $1$ to get $T_4=\{2,5\}$.
• Fifth operation: Union $T_3$ and $T_4$ to get $T_5=\{1,2,4,5\}$. This results in $T$.

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

Note

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