Little W has been forced into a game of Nim!

There are $n$ piles of stones in front of W, numbered from $1$ to $n$, where the $i$-th pile contains $a_i$ stones. In the game of Nim, W and a brilliant opponent take turns. W goes second. In each turn, a player can choose one pile and remove any number of stones from that pile, but they must remove at least one. If a player cannot make a move because there are no stones left in any of the $n$ piles, they lose.

W, who is well-versed in OI knowledge, knows the optimal strategy for the game of Nim. He knows that if both players play optimally, the second player wins if and only if the XOR sum of all $a_i$ is $0$. However, the initial state does not necessarily satisfy this condition, so W decides to use some "extra-game" tactics to make the XOR sum of all $a_i$ equal to $0$ and win the game. To do this, W has prepared many stones. Before the game starts, he can add any number of stones (including zero) to each pile. However, W cannot remove stones from the piles, nor can he create new piles.

W asks you to provide a plan for adding stones. To remain covert, W wants to add as few stones as possible, so he first needs to know the minimum number of stones that need to be added. In addition, he wants to prepare $m$ different plans for adding the minimum number of stones, just in case. We consider two plans to be different if and only if there exists at least one pile where the number of stones added in the two plans is different. If there are fewer than $m$ such plans, you need to tell him all of them; if there are more than $m$ such plans, you can provide any $m$ of them.

Input

The input contains multiple test cases.

The first line contains two integers $c$ and $T$, representing the test case ID and the number of test cases. For the sample, $c = 0$.

For each test case: The first line contains two integers $n$ and $m$, representing the number of piles and the number of plans W needs. The second line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$, describing the number of stones in each pile.

Output

For each test case: The first line contains an integer $k$, representing the minimum number of stones W needs to add. The second line contains an integer $m'$, representing the number of plans you provide to W. If the number of plans that add the minimum number of stones is less than $m$, you must ensure $m' = m$, otherwise you must ensure $m'$ is exactly the number of plans that add the minimum number of stones. Then output $m'$ different plans sequentially. For each plan, output three lines: The first line contains an integer $n'$, representing the number of piles to which stones were added in this plan. The second line contains $n'$ integers $x_1, x_2, \dots, x_{n'}$, describing the indices of the piles to which stones were added. You must ensure $1 \le x_1 < x_2 < \dots < x_{n'} \le n$. If $n' = 0$, this line should be an empty line. The third line contains $n'$ integers $w_1, w_2, \dots, w_{n'}$, where $w_j$ ($1 \le j \le n'$) represents the number of stones added to the pile with index $x_j$. You must ensure that for any $1 \le j \le n'$, $w_j \ge 1$ and $\sum_{j=1}^{n'} w_j = k$. If $n' = 0$, this line should be an empty line.

You must ensure that the total number of integers output in a single test case does not exceed $10^7$. It is guaranteed that such an output satisfying the problem conditions always exists.

Examples

Input 1

0 2
3 1
4 2 3
2 2
1 3

Output 1

3
1
2
1 3
2 1
2
1
1
1
1
2

Note 1

For the first test case, W has two plans that add the minimum number of stones: Add 2 stones to pile 1 and 1 stone to pile 3. The three piles become 6, 2, 4, and the second player wins. Add 3 stones to pile 3. The three piles become 4, 2, 6, and the second player wins.

Since W only needs one plan, outputting either one is acceptable; the sample output provides the first one.

For the second test case, W has only one plan that adds the minimum number of stones: * Add 2 stones to pile 1. The two piles become 3, 3, and the second player wins.

Although W requested two plans, since there is only one, outputting the only one is sufficient.

Input 2

See nim/nim2.in and nim/nim2.ans in the contestant directory.

Constraints

Let $\sum n$ and $\sum m$ denote the sum of $n$ and $m$ over all test cases in a single test point, respectively. For all test cases, it is guaranteed that: $1 \le T \le 2 \times 10^4$; $2 \le n \le 10^5$, $2 \le \sum n \le 2 \times 10^5$, $1 \le m, \sum m \le 2 \times 10^4$; For any $1 \le i \le n$, $0 \le a_i \le 2^{60} - 1$; $\sum_{i=1}^n a_i \ge 1$.

Special Property A: For any $1 \le i \le n$, $a_i$ is a non-negative power of 2. Special Property B: $a_1 = 0$.

Scoring

For each test point, if you correctly output the minimum number of stones W needs to add (i.e., $k$ in the output format) for all test cases, you will receive 50% of the points for that test point. On this basis, if you also provide the plans according to the requirements for all test cases, you will receive 100% of the points for that test point.

Note that even if you only want to answer the minimum number of stones W needs, you still need to output the number of plans and the corresponding, correct, non-repeating plans in the given format after answering the minimum number of stones. Simply outputting $m' = 0$ is sufficient to complete this.