当你还是个孩子的时候,你一定听说过一个关于袋子和硬币的拼图。无论如何,这是它的版本之一:
一匹马有三个袋子。第一个袋子有一个硬币,第二个袋子有一个硬币,第三个袋子有三个硬币。这匹马的袋子里总共有三枚硬币。这怎么可能?
答案很简单。第三个袋子里有一枚硬币和另外两个袋子。
这个问题是童年难题的概括。你有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
注意
下图显示了从语句中解决一个测试用例的两种可能方法。左图对应第一个测试用例,右图对应第二个测试用例。