Constructing a Target Subset

Given a positive integer \(n\) and a non‐negative integer \(m\), consider the universe \(U = \{1,2,\ldots,n\}\). We define \((n+m)\) sets \(A_1,A_2,\ldots,A_{n+m}\) as follows:

• For \(1 \le i \le n\), \(A_i\) is the set of all multiples of \(i\) in \(U\), i.e. \(A_i = \{j \in U : i \mid j\}\).
• For \(n+1 \le i \le n+m\), there is an associated operation parameter \(op_i\) which is one of the following:
  • If \(op_i = 1\), two parameters \(x,y\) are given with \(x,y < i\) and then \(A_i = A_x \cup A_y\).
  • If \(op_i = 2\), two parameters \(x,y\) are given with \(x,y < i\) and then \(A_i = A_x \cap A_y\).
  • If \(op_i = 3\), a parameter \(x\) is given with \(x < i\) and then \(A_i = U \setminus A_x\) (i.e. the complement of \(A_x\) in \(U\)).

The answer to the problem is defined to be \(A_{n+m}\).

You are given a positive integer \(n\) and a target set \(B \subseteq \{1,2,\ldots,n\}\). Your task is to construct a non‐negative integer \(m\) (with \(0 \le m \le 10^5\)) and a sequence of parameters (i.e. a sequence of operations as described above) so that the final set \(A_{n+m}\) equals \(B\). It can be proved that a solution always exists.

inputFormat

The input consists of two lines:

1. The first line contains two integers \(n\) and \(k\), where \(n\) is the size of the universe \(U = \{1, 2, \ldots, n\}\) and \(k\) is the number of elements in the target set \(B\).
2. The second line contains \(k\) distinct integers \(b_1, b_2, \ldots, b_k\) (each between 1 and \(n\)) denoting the elements of \(B\). (If \(k=0\), the second line may be empty.)

The numbers on each line are separated by spaces.

outputFormat

First, output an integer \(m\) (the number of operations you used to construct the final set). Then output \(m\) lines, each describing one operation.

Each operation is in one of the following formats:

• For a union operation: 1 x y (which means: create a new set as the union of set \(A_x\) and \(A_y\)).
• For an intersection operation: 2 x y (which means: create a new set as the intersection of set \(A_x\) and \(A_y\)).
• For a complement operation: 3 x (which means: create a new set as the complement of \(A_x\) in \(U\)).

The indices \(x\) (and \(y\) if applicable) refer to previously defined sets. The initial sets have indices from 1 to \(n\) (where \(A_i\) is defined as the set of multiples of \(i\) in \(U\)). The new sets you create are numbered \(n+1, n+2, \ldots, n+m\) in the order of creation. Your final answer is the set with index \(n+m\), which must equal \(B\).

You may output any valid sequence of operations that meets the constraints.

sample

6 2
2 3

7
3 4
2 2 7
3 6
2 8 9
3 6
2 3 11
1 10 12