In this problem, we consider a sequence of $n + m$ subsets of the set $\{1, \dots, n\}$. The sets $A_1, \dots, A_n$ are defined as follows: a value $1 \le i \le n$ belongs to the set $A_j$ if and only if $i$ is divisible by $j$.

For example, for $n = 7$, the initial sets are: $A_1 = \{1, 2, 3, 4, 5, 6, 7\}$ $A_2 = \{2, 4, 6\}$ $A_3 = \{3, 6\}$ $A_4 = \{4\}$ $A_5 = \{5\}$ $A_6 = \{6\}$ * $A_7 = \{7\}$

The subsequent $m$ sets—$A_{n+1}, A_{n+2}, \dots, A_{n+m}$—are created using union, intersection, or negation operations on previous sets. The union operation of sets $A_i$ and $A_j$ (denoted by $A_i \cup A_j$) creates a set containing all numbers belonging to either $A_i$ or $A_j$. The intersection operation of sets $A_i$ and $A_j$ (denoted by $A_i \cap A_j$) creates a set containing all numbers belonging to both $A_i$ and $A_j$. * The negation operation of set $A_i$ (denoted by $A'_i$) creates a set containing all integers $1 \le j \le n$ that do not belong to $A_i$.

An example sequence of operations might look as follows: $A_8 = A_5 \cup A_7 = \{5, 7\}$ $A_9 = A_2 \cap A_3 = \{6\}$ $A_{10} = A'_8 = \{1, 2, 3, 4, 6\}$ $A_{11} = A_{10} \cap A_8 = \{\}$ $A_{12} = A'_3 = \{1, 2, 4, 5, 7\}$ $A_{13} = A_{12} \cup A_{12} = \{1, 2, 4, 5, 7\}$ $A_{14} = A_{10} \cap A_{13} = \{1, 2, 4\}$ $A_{15} = A_9 \cup A_{14} = \{1, 2, 4, 6\}$

Given the number $n$ and a target set $B$, your task is to choose the number $m$ ($0 \le m \le 100\,000$) and a sequence of $m$ operations such that the set $A_{n+m}$ is equal to the set $B$. It can be proven that for the limits given in the problem, it is possible to construct any subset of $\{1, \dots, n\}$ within the operation limit.

Input

The first line of input contains two integers $n, s$ ($1 \le n \le 50\,000, 1 \le s \le n$), representing the number of initial sets and the size of the target set $B$, respectively. The second line contains a sequence of $s$ integers $b_1, b_2, \dots, b_s$ ($1 \le b_1 < b_2 < \dots < b_s \le n$), containing the elements of set $B$.

Output

The first line of output should contain the integer $m$ ($0 \le m \le 100\,000$). The following $m$ lines should contain descriptions of the subsequent operations. Line $i$, describing how the set $A_{n+i}$ was created, should be in one of the following three formats: 1 x y – representing the union operation $A_{n+i} = A_x \cup A_y$, 2 x y – representing the intersection operation $A_{n+i} = A_x \cap A_y$, * 3 x – representing the negation operation $A_{n+i} = A'_x$.

Additionally, the condition $A_{n+m} = B$ must be satisfied.

Examples

Input 1

7 4
1 2 4 6

Output 1

8
1 5 7
2 2 3
3 8
2 10 8
3 3
1 12 12
2 10 13
1 9 14

Input 2

3 1
3

Output 2

0

Note

The first example test corresponds to the example operations described in the problem statement. In the second case, no operations are needed, as $A_n = B$.