← 返回题目列表

Codeforces · 356/D

D. 袋子和硬币

中文机器翻译题面 查看原题

当你还是个孩子的时候,你一定听说过一个关于袋子和硬币的拼图。无论如何,这是它的版本之一:

一匹马有三个袋子。第一个袋子有一个硬币,第二个袋子有一个硬币,第三个袋子有三个硬币。这匹马的袋子里总共有三枚硬币。这怎么可能?

答案很简单。第三个袋子里有一枚硬币和另外两个袋子。

这个问题是童年难题的概括。你有n袋。你知道第一个袋子里有a1个硬币,第二个袋子里有a2个硬币,……,第n个袋子里有一个硬币。总共有 s 个硬币。找到排列袋子和硬币的方法,使它们符合所描述的场景,否则说明这是不可能的。

输入

第一行包含两个整数 n 和 s (1 ≤ n, s ≤ 70000) — 袋子数量和硬币总数。下一行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 70000),其中 ai 表示第 i 个袋子中的硬币数量。

输出

如果答案不存在,则打印-1。

否则,打印n行,在第i行打印第i个包的内容。该行中的第一个数字 ci (0 ≤ ci ≤ ai) 必须表示直接位于第 i 个袋子中的硬币数量(不考虑第 i 个袋子中的袋子中的硬币)。行中的第二个数字 ki (0 ≤ ki < n) 必须表示直接位于第 i 个袋子中的袋子的数量(不考虑位于第 i 个袋子中的袋子内部的袋子)。接下来,该行必须包含 ki 个整数——直接位于第 i 个袋子中的袋子的编号。

溶液中的硬币总数必须等于 s。如果我们计算解决方案中第 i 个袋子的硬币总数,我们应该得到 ai。

任何袋子不能直接放入多个袋子中。这些袋子可以嵌套在不止一层中(参见第二个测试用例)。如果有多个正确答案,您可以打印其中任何一个。

示例

输入 #1

3 3
1 3 1

输出 #1

1 0
1 2 3 1
1 0

输入 #2

3 3
1 3 1

输出 #2

1 0
2 1 3
0 1 1

输入 #3

1 2
1

输出 #3

-1

输入#4

8 10
2 7 3 4 1 3 1 2

输出#4

2 0
1 2 1 4
0 2 7 8
0 2 5 6
1 0
3 0
1 0
2 0

注意

下图显示了从语句中解决一个测试用例的两种可能方法。左图对应第一个测试用例,右图对应第二个测试用例。