#1851. 「NOI2020」制作菜品

「NOI2020」制作菜品

题目描述

厨师准备给小朋友们制作 mm 道菜,每道菜均使用 kk 克原材料。为此,厨师购入了 nn 种原材料,原材料从 11nn 编号,第 ii 种原材料的质量为 did_i 克。nn 种原材料的质量之和恰好为 m×km\times k,其中 did_ikk 都是正整数

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

  • 共做出 mm 道菜。

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

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

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

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

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

输入格式

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

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

第一行一个整数 TT 表示数据组数。对于每组数据:

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

  • 第二行 nn 个整数,第 ii 个整数表示第 ii 种原材料的质量 did_i

输出格式

输出到文件 dish.out 中。

对于每组测试数据:

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

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

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

    • 依次输出一行四个整数 iixxjjyy,表示该道菜使用 xx 克第 ii 种原材料与 yy 克第 jj 种原材料制作。你应保证 1i,jn1\le i, j\le niji \neq jx+y=kx + y = kx,y>0x, y > 0

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

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

样例

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

对于第二组数据,一种满足要求的制作方案为:

  • 使用 8080 克原材料 112020 克原材料 22 做第一道菜。
  • 使用 1010 克原材料 229090 克原材料 33 做第二道菜。
  • 使用 100100 克原材料 44 做第三道菜。

见附加文件中的 dish2.indish2.ans

见附加文件中的 dish3.indish3.ans

数据范围与提示

对于所有测试点:

1T101\le T\le 101n5001\le n\le 500n2m5000n - 2\le m\le 5000m1m\ge 1
1k50001\le k\le 5000i=1ndi=m×k\sum_{i=1}^n d_i=m\times k

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

测试点编号 nn mm kk
131\sim 3 4\le 4 50\le 50
454\sim 5 10\le 10 5000\le 5000
676\sim 7 500\le 500 =n1= n-1
898\sim 9 n1m5000n-1\le m\le 5000
1010 25\le 25 5000\le 5000
111211\sim 12 500\le 500
131413\sim 14 50\le 50
151715\sim 17 100\le 100 5000\le 5000
182018\sim 20 500\le 500