## NOI '20 P4 - Dish

View as PDF

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem types

The chef is preparing dishes, and each dish uses grams of ingredients. As a result, the chef has bought ingredients, and the ingredients are numbered . The -th ingredient weighs grams. The sum of weights of all ingredients is exactly grams. and 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 dishes. More formally, the final plan shall satisfy the following requirements:

1. Prepare dishes in total.

2. Each dish uses at most 2 ingredients.

3. Each dish uses exactly grams of ingredients.

4. For each ingredient used in a given dish, the amount used is a positive integer measured in grams.

5. All of the ingredients will be completely utilized.

If there exists a feasible solution, you should output a detailed plan.

#### Input Specification

In this problem, each test case may have multiple instances. The first line is an integer denoting the number of instances. For each instance, the first line contains three positive integers denoting the number of ingredients, the number of dishes to prepare, and the amount of ingredients each dish uses. The second line contains integers, and the -th integer denotes there are grams of ingredient .

#### Output Specification

For each instance, if there is no feasible solution, output -1. Otherwise, you need to output 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:

• a line containing two integers and denoting the dish will use grams of ingredient . Here, and .
• a line containing four integers denoting the dish will use grams of ingredient and grams of ingredient . Here, , , , .

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.

#### Sample Input

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

#### Sample Output

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

For all test cases:
, , , ,
, .

Test case
1~3
4~5
6~7
8~9
10
11~12
13~14
15~17
18~20