Divide and Conquer Multiplication Challenge

Given a target set \(T \subset \{1,2,\dots,n\}\) (with \(1 \le n \le 5\times10^5\)), you are required to construct \(T\) using a series of operations. The allowed operations are:

• Create: Create a set of size 1. That is, you form a set \(S = \{x\}\) for some integer \(x\).
• Union: Given two disjoint sets \(A\) and \(B\) that have been constructed, you can form \(A \cup B\). (The resulting set is assigned a new ID.)
• Shift: Given a constructed set \(A\), you can shift it by an integer \(x\) to obtain \(A+x = \{a+x : a \in A\}\).

Note that any set you construct may be re-used in later operations, but every set created throughout the process must be a subset of \(\{1, 2, \dots, n\}\). The cost is defined as the sum of the sizes of all constructed sets. You do not need to minimize this cost; you only need to ensure that the total cost does not exceed \(5\times10^6\) and the number of operations does not exceed \(10^6\).

inputFormat

The input consists of the following:

1. A line containing one integer \(n\) \((1 \le n \le 5\times10^5)\).
2. A line containing an integer \(k\) representing the number of elements in the target set \(T\).
3. A line containing \(k\) distinct integers, each between 1 and \(n\), representing the elements of \(T\). (The order of the elements is arbitrary.)

outputFormat

Output a valid sequence of operations to construct the target set \(T\) as follows:

1. First, print a line containing the integer \(m\), the total number of operations.
2. Then print \(m\) lines, each of which describes one operation. The operations are encoded as:
   • 1 x: Create a set \(\{x\}\). (This operation gets a new ID.)
   • 2 a b: Union the two sets with IDs a and b (which must be disjoint), forming \(A \cup B\). The new set is then assigned a new ID.
   • 3 a x: Shift the set with ID a by \(x\), i.e. replace it with \(A+x = \{a+x : a \in A\}\).

The final set produced by these operations must equal \(T\).

sample

5
2
2 4

3
1 2
1 4
2 1 2