P6775 [NOI2020] Cooking Dishes

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.

**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$.

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**.

#### 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: | Test Point ID | $n$ | $m$ | $k$ | | :-: | :-: | :-: | :-: | | $1\sim 3$ | $\le 4$ | $\le 4$ | $\le 50$ | | $4\sim 5$ | $\le 10$ | $\le 10$ | $\le 5\times 10^3$ | | $6\sim 7$ | $\le 500$ | $=n-1$ | $\le 5\times 10^3$ | | $8\sim 9$ | $\le 500$ | $n-1\le m\le 5\times 10^3$ | $\le 5\times 10^3$ | | $10$ | $\le 25$ | $\le 5\times 10^3$ | $\le 5\times 10^3$ | | $11\sim 12$ | $\le 25$ | $\le 5\times 10^3$ | $\le 500$ | | $13\sim 14$ | $\le 50$ | $\le 5\times 10^3$ | $\le 500$ | | $15\sim 17$ | $\le 100$ | $\le 5\times 10^3$ | $\le 5\times 10^3$ | | $18\sim 20$ | $\le 500$ | $\le 5\times 10^3$ | $\le 5\times 10^3$ | Translated by ChatGPT 5