B. Integer Generator
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Given a set of integers $$$S$$$, your task is to generate a given integer $$$x$$$ using no more than $$$70$$$ bitwise operations on $$$S$$$.

Specifically, given an integer set $$$S$$$ of size $$$n$$$ and an integer $$$x$$$, each operation allows you to choose two integers $$$a$$$ and $$$b$$$ from $$$S$$$ (they can be the same) and insert one of the integers $$$a\ \texttt{or}\ b$$$, $$$a\oplus b$$$, or $$$a\ \texttt{and}\ b$$$ into $$$S$$$. You need to determine whether it is possible to make $$$x\in S$$$ with no more than $$$70$$$ operations, and if so, provide a valid sequence of operations.

Here, $$$a\ \texttt{or}\ b$$$ refers to the bitwise OR of $$$a$$$ and $$$b$$$, $$$a\oplus b$$$ refers to the bitwise XOR of $$$a$$$ and $$$b$$$, and $$$a\ \texttt{and}\ b$$$ refers to the bitwise AND of $$$a$$$ and $$$b$$$.

Input

The first line contains two integers $$$n,x$$$ ($$$1\le n\le 10^5,0\le x \lt 2^{30}$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots ,a_n$$$ ($$$0\le a_i \lt 2^{30}$$$), representing the initial elements in $$$S$$$, ensuring that these integers are all distinct.

Output

If it is not possible to make $$$x\in S$$$ with no more than $$$70$$$ operations, output a single integer $$$-1$$$.

Otherwise, output the first line with an integer $$$k$$$ ($$$0\le k\le 70$$$), indicating the number of operations.

Next, output $$$k$$$ lines, each representing one of the $$$k$$$ operations. For each operation, output three integers $$$t,a,b$$$ ($$$t\in \{0,1,2\}$$$). If $$$t=0$$$, it means this operation inserts $$$a\ \texttt{or}\ b$$$ into $$$S$$$; if $$$t=1$$$, it means it inserts $$$a\oplus b$$$ into $$$S$$$; if $$$t=2$$$, it means it inserts $$$a\ \texttt{and}\ b$$$ into $$$S$$$. You need to ensure that for the $$$S$$$ before this operation, both $$$a\in S$$$ and $$$b\in S$$$ should be met.

In this problem, you do not need to minimize the number of operations; if there are multiple valid operation sequences, any one of them will be accepted.

Examples
Input
3 7
1 2 4
Output
2
1 1 2
1 3 4
Input
3 15
9 10 4
Output
2
0 10 9
1 4 11
Input
3 7
1 2 3
Output
-1