| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 24 | 9 | 7 | 33.333% |
The chef is preparing $m$ dishes, and each dish uses $k$ grams of ingredients. As a result, the chef has bought $n$ ingredients, and the ingredients are numbered $1, 2, \dots, n$. The $i$-th ingredient weighs $d_i$ grams. The sum of weights of all $n$ ingredients is exactly $m \times k$ grams. $d_i$ and $k$ are positive integers.
An ingredient may be used in multiple dishes. However, each dish may use at most 2 ingredients. Now you are asked to decide if there exists a valid way to prepare the $m$ dishes. More formally, the final plan shall satisfy the following requirements:
If there exists a feasible solution, you should output a detailed plan.
In this problem, each test case may have multiple instances. The first line is an integer $T$ denoting the number of instances. For each instance, the first line contains three positive integers $n,m,k$ denoting the number of ingredients, the number of dishes to prepare, and the amount of ingredients each dish uses. The second line contains $n$ integers, and the $i$-th integer denotes there are $a_i$ grams of ingredient $i$.
For each instance, if there is no feasible solution, output -1. Otherwise, you need to output $m$ lines, and each line specifies the way to prepare a dish. Depending on the number of ingredients used in the dish, a line shall be in one of the following two formats:
Your answer will be checked by a special judge. Therefore, if there are multiple feasible solutions, you may print any solution. You should make sure the output is in the correct format, and two adjacent integers in a line are separated by a single space. Finally, your output shall not contain any 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
$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\limits_{i=1}^n d_i = m \times k$.