Little w has been dragged into a game of Nim that decides everything!

There are $n$ piles of stones in front of little w, numbered from $1$ to $n$, where the $i$-th pile contains $a_i$ stones. In the game of Nim, little w and an extremely clever opponent take turns. Little w goes second. In each turn, a player can choose one pile and remove any number of stones from that pile, but they cannot choose to remove zero stones. If a player is to make a move and all $n$ piles have zero stones, they cannot make a move and thus lose.

Little w, who is proficient in OI knowledge, knows the optimal strategy for Nim. He also 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 little w decides to use some "outside" tricks to make the XOR sum of all $a_i$ equal to $0$, and then win the game. To this end, little w has prepared many stones. He can add any number of stones (including zero) to each pile before the game starts. However, little w cannot remove stones from the piles, nor can he create new piles.

Little w asks you to provide a plan for adding stones. To remain covert, little 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 also wants to prepare $m$ different plans for adding stones, just in case. We consider two plans to be different if and only if there exists some 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 is read from the file nim.in.

There are multiple test cases in this problem.

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

Then, for each test case: The first line contains two integers $n$ and $m$, representing the number of stone piles and the number of plans little 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

The output is written to the file nim.out.

For each test case: The first line contains an integer $k$, representing the minimum number of stones little w needs to add. The second line contains an integer $m'$, representing the number of plans you provide to little w. If the number of plans with the minimum number of added stones is no less than $m$, you must ensure $m' = m$; otherwise, you must ensure $m'$ is exactly the number of plans with the minimum number of added stones. Then, output $m'$ different plans in sequence. For each plan, output three lines, where: 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 in this plan. 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$ in this plan. 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 point does not exceed $10^7$. It is guaranteed that there always exists an output satisfying the problem conditions.

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$, $\sum n \le 2 \times 10^5$, $1 \le m, \sum m \le 2 \times 10^4$, $\forall 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 every $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 little w needs (i.e., $k$ in the output format) for all test cases, you will receive 50% of the score for that test point. On this basis, if you provide the plans according to the requirements for all test cases, you will receive 100% of the score for that test point. The score of a subtask depends on the minimum score of the test points within that subtask.

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

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
2

Note 1

For the first test case, little w has two plans that minimize the total number of added stones: Add 2 stones to the 1st pile, and add 1 stone to the 3rd pile. The three piles then become 6, 2, 4, and the second player wins. Add 3 stones to the 3rd pile. The three piles then become 4, 2, 6, and the second player wins.

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

For the second test case, little w has only one plan that minimizes the total number of added stones: * Add 2 stones to the 1st pile. The two piles then become 3, 3, and the second player wins.

Although little w needs 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.