A85955.「NOI2020」制作菜品

厨师准备给小朋友们制作 $m$ 道菜，每道菜均使用 $k$ 克原材料。为此，厨师购入了 $n$ 种原材料，原材料从 $1$ 到 $n$ 编号，第 $i$ 种原材料的质量为 $d_i$ 克。$n$ 种原材料的质量之和恰好为 $m\times k$ 克，其中 $d_i$ 与 $k$ 都是正整数。

制作菜品时，一种原材料可以被用于多道菜，但为了让菜品的味道更纯粹，厨师打算每道菜至多使用 $2$ 种原材料。现在请你判断是否存在一种满足要求的制作方案。更具体地，方案应满足下列要求：

• 共做出 $m$ 道菜。

• 每道菜至多使用 $2$ 种原材料。

• 每道菜恰好使用 $k$ 克原材料。

• 每道菜使用的每种原材料的质量都为正整数克。

• $n$ 种原材料都被恰好用完。

若存在满足要求的制作方案，你还应该给出一种具体的制作方案。

从文件 dish.in 中读入数据。

本题单个测试点包含多组测试数据。

第一行一个整数 $T$ 表示数据组数。对于每组数据：

• 第一行三个正整数 $n, m, k$ 分别表示原材料种数、需要制作的菜品道数、每道菜品需使用的原材料的质量。

• 第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 种原材料的质量 $d_i$。

输出到文件 dish.out 中。

对于每组测试数据：

• 若不存在满足要求的制作方案，则输出一行一个整数 $-1$；

• 否则你需要输出 $m$ 行，每行表示一道菜品的制作方案，根据使用的原材料种数，格式为下列两种之一：

  • 依次输出一行两个整数 $i$ 和 $x$，表示该道菜使用 $x$ 克第 $i$ 种原材料制作。你应保证 $1\le i\le n, x = k$。

  • 依次输出一行四个整数 $i$、$x$、$j$ 和 $y$，表示该道菜使用 $x$ 克第 $i$ 种原材料与 $y$ 克第 $j$ 种原材料制作。你应保证 $1\le i, j\le n$，$i \neq j$，$x + y = k$，$x, y > 0$。

本题使用自定义校验器检验你的答案是否正确，因此若有多种满足条件的方案，你只需要输出任意一种。

你应保证方案输出的格式正确，且同一行中相邻的两个数使用单个空格分隔，除此之外你的输出中不应包含其他多余字符。

对于所有测试点：

$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$。

每个测试点的具体限制见下表：

测试点编号	$n$	$m$	$k$
$1\sim 3$	$\le 4$	$\le 4$	$\le 50$
$4\sim 5$	$\le 10$	$\le 10$	$\le 5000$
$6\sim 7$	$\le 500$	$= n-1$	$\le 5000$
$8\sim 9$	$\le 500$	$n-1\le m\le 5000$	$\le 5000$
$10$	$\le 25$	$\le 5000$	$\le 5000$
$11\sim 12$	$\le 25$	$\le 5000$	$\le 500$
$13\sim 14$	$\le 50$	$\le 5000$	$\le 500$
$15\sim 17$	$\le 100$	$\le 5000$	$\le 5000$
$18\sim 20$	$\le 500$	$\le 5000$	$\le 5000$