A chef is preparing $m$ dishes for children, with each dish requiring $k$ grams of raw materials. To this end, the chef has purchased $n$ types of raw materials, numbered from $1$ to $n$, where the mass of the $i$-th raw material is $d_i$ grams. The sum of the masses of the $n$ raw materials is exactly $m \times k$ grams, where both $d_i$ and $k$ are positive integers.

When preparing the dishes, one type of raw material can be used for multiple dishes, but to keep the flavor of the dishes pure, the chef intends to use at most $2$ types of raw materials for each dish. Now, please determine whether there exists a preparation plan that meets the requirements. More specifically, the plan should satisfy the following requirements:

• A total of $m$ dishes are made.
• Each dish uses at most $2$ types of raw materials.
• Each dish uses exactly $k$ grams of raw materials.
• The mass of each type of raw material used in each dish is a positive integer in grams.
• All $n$ types of raw materials are used up exactly.

If a valid preparation plan exists, you should also provide a specific plan.

Input

The input is read from the file dish.in. This problem contains multiple test cases. The first line contains an integer $T$ representing the number of test cases. For each test case:

• The first line contains three positive integers $n, m, k$, representing the number of types of raw materials, the number of dishes to be prepared, and the mass of raw materials required for each dish, respectively.
• The second line contains $n$ integers, where the $i$-th integer represents the mass $d_i$ of the $i$-th raw material.

Output

The output is written to the file dish.out. For each test case:

• If no valid preparation plan exists, output a single integer $-1$.
• Otherwise, you need to output $m$ lines, each representing the preparation plan for one dish. Depending on the number of raw material types used, the format should be one of the following two:
  • Output two integers $i$ and $x$, indicating that the dish is made using $x$ grams of the $i$-th raw material. You must ensure $1 \le i \le n$ and $x = k$.
  • Output four integers $i, x, j, y$, indicating that the dish is made using $x$ grams of the $i$-th raw material and $y$ grams of the $j$-th raw material. You must ensure $1 \le i, j \le n$, $i \neq j$, $x + y = k$, and $x, y > 0$.

This problem uses a custom checker to verify the correctness of your answer, so if there are multiple valid plans, you only need to output any one of them. You must ensure that the output format is correct, and that the two numbers on the same line are separated by a single space; apart from this, your output should not contain any other extra characters.

Examples

Input 1

4
1 1 10
10
4 3 100
80 30 90 100
5 3 1000
200 400 500 900 1000
6 4 100
25 30 50 80 95 120

Output 1

1 10
1 80 2 20
2 10 3 90
4 100
-1
1 5 5 95
1 20 4 80
2 30 6 70
3 50 6 50

Note

For the second test case, one valid preparation plan is: Use $80$ grams of raw material $1$ and $20$ grams of raw material $2$ to make the first dish. Use $10$ grams of raw material $2$ and $90$ grams of raw material $3$ to make the second dish. * Use $100$ grams of raw material $4$ to make the third dish.

Examples 2

See dish/dish2.in and dish/dish2.ans in the contestant directory.

Examples 3

See dish/dish3.in and dish/dish3.ans in the contestant directory.

Constraints

For all test cases: $1 \le T \le 10$, $1 \le n \le 500$, $n - 2 \le m \le 5000$, $m \ge 1$, $1 \le k \le 5000$, $\sum_{i=1}^n d_i = m \times k$.