Description

A chef plans to cook $m$ dishes for kids, and each dish uses $k$ grams of ingredients. For this purpose, the chef bought $n$ types of ingredients, numbered from $1$ to $n$. The mass of ingredient type $i$ is $d_i$ grams. The total mass of all $n$ ingredients is exactly $m \times k$ grams, where both $d_i$ and $k$ are positive integers.

When cooking, one type of ingredient may be used in multiple dishes. However, to make the taste purer, the chef decides that each dish uses at most $2$ types of ingredients. Now you need to determine whether there exists a cooking plan that satisfies the requirements. More specifically, the plan must satisfy:

• A total of $m$ dishes are made.
• Each dish uses at most $2$ types of ingredients.
• Each dish uses exactly $k$ grams of ingredients.
• The amount of each ingredient used in each dish is a positive integer number of grams.
• All $n$ types of ingredients are used up exactly.

If such a plan exists, you also need to output one specific plan.

Input Format

This problem contains multiple test cases in a single test file.

The first line contains an integer $T$ denoting the number of test cases. For each test case:

• The first line contains three positive integers $n, m, k$, representing the number of ingredient types, the number of dishes to cook, and the grams of ingredients needed per dish.
• The second line contains $n$ integers; the $i$-th integer denotes $d_i$, the mass of ingredient type $i$.

Output Format

For each test case:

• If no feasible cooking plan exists, output one line with the integer $-1$.
• Otherwise, output $m$ lines, each describing one dish. Depending on how many ingredient types are used, the format is one of the following:
  • Output two integers $i$ and $x$, meaning this dish uses $x$ grams of ingredient type $i$. You must ensure $1 \leq i \leq n$ and $x = k$.
  • Output four integers $i$, $x$, $j$, and $y$, meaning this dish uses $x$ grams of ingredient type $i$ and $y$ grams of ingredient type $j$. You must ensure $1 \leq i, j \leq n$, $i \not= j$, $x + y = k$, and $x, y > 0$.

This problem uses a custom checker to verify your output, so if multiple valid plans exist, you only need to output any one of them.

You must ensure the output format is correct. Adjacent numbers on the same line must be separated by exactly one space, and your output must not contain any other extra characters.

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

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

Hint

Sample 1 Explanation

For the second test case, one feasible cooking plan is:

• Use $80$ grams of ingredient $1$ and $20$ grams of ingredient $2$ to make the first dish.
• Use $10$ grams of ingredient $2$ and $90$ grams of ingredient $3$ to make the second dish.
• Use $100$ grams of ingredient $4$ to make the third dish.

Sample 2

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

Sample 3

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

Constraints

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

The specific limits for each test point are shown in the table below:

Translated by ChatGPT 5