CF356D.Bags and Coins

When you were a child you must have been told a puzzle of bags and coins. Anyway, here's one of its versions:

A horse has three bags. The first bag has one coin, the second bag has one coin and the third bag has three coins. In total, the horse has three coins in the bags. How is that possible?

The answer is quite simple. The third bag contains a coin and two other bags.

This problem is a generalization of the childhood puzzle. You have n bags. You know that the first bag contains _a_1 coins, the second bag contains _a_2 coins, ..., the n-th bag contains a__n coins. In total, there are s coins. Find the way to arrange the bags and coins so that they match the described scenario or else state that it is impossible to do.

小时候，你一定听过一个关于袋子和硬币的谜题。无论如何，以下是该谜题的一个版本：

一匹马有三个袋子。第一个袋子有一枚硬币，第二个袋子有一枚硬币，第三个袋子有三枚硬币。然而，马在所有袋子中总共只有三枚硬币。这怎么可能？

答案非常简单：第三个袋子中包含一枚硬币以及另外两个袋子。

本题是上述儿童谜题的一个推广。你有 $n$ 个袋子。已知第一个袋子包含 $a_1$ 枚硬币，第二个袋子包含 $a_2$ 枚硬币，……，第 $n$ 个袋子包含 $a_n$ 枚硬币。而所有袋子中硬币的总数为 $s$。请找出一种将袋子与硬币进行嵌套安排的方式，使其满足上述描述的情形；若无法做到，则说明这是不可能的。

The first line contains two integers n and s (1 ≤ n, s ≤ 70000) — the number of bags and the total number of coins. The next line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 70000), where a__i shows the number of coins in the i-th bag.

第一行包含两个整数 $n$ 和 $s$（$1 \leq n, s \leq 70000$）—— 分别表示袋子的数量和硬币的总数。
接下来一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 70000$），其中 $a_i$ 表示第 $i$ 个袋子中的硬币数量。

If the answer doesn't exist, print -1.

Otherwise, print n lines, on the i-th line print the contents of the i-th bag. The first number in the line, c__i (0 ≤ c__i ≤ a__i), must represent the number of coins lying directly in the i-th bag (the coins in the bags that are in the i-th bag are not taken into consideration). The second number in the line, k__i (0 ≤ k__i < n) must represent the number of bags that lie directly in the i-th bag (the bags that are inside the bags lying in the i-th bag are not taken into consideration). Next, the line must contain k__i integers — the numbers of the bags that are lying directly in the i-th bag.

The total number of coins in the solution must equal s. If we count the total number of coins the i-th bag in the solution has, we should get a__i.

No bag can directly lie in more than one bag. The bags can be nested in more than one level (see the second test case). If there are multiple correct answers, you can print any of them.

如果答案不存在，输出 -1。

否则，输出 n 行，其中第 i 行表示第 i 个袋子的内容。该行的第一个数 c_i（满足 0 ≤ c_i ≤ a_i）表示直接放在第 i 个袋子中的硬币数量（不计入放在第 i 个袋子内部的其他袋子中的硬币）。该行的第二个数 k_i（满足 0 ≤ k_i < n）表示直接放在第 i 个袋子中的袋子数量（不计入放在这些袋子内部的更深层袋子）。接下来，该行还需包含 k_i 个整数——即直接放在第 i 个袋子中的那些袋子的编号。

解中硬币总数必须等于 s。若统计解中第 i 个袋子所含的硬币总数（包括其自身含有的硬币以及其所有嵌套子袋中的硬币），结果应恰好为 a_i。

任意一个袋子不能直接属于超过一个袋子（即不能同时作为两个不同袋子的直接子袋）。袋子可以嵌套多层（参见第二个测试用例）。若存在多个正确答案，输出任意一个即可。

The pictures below show two possible ways to solve one test case from the statement. The left picture corresponds to the first test case, the right picture corresponds to the second one.

下图展示了题面中一个测试用例的两种可能解法。左侧图片对应第一个测试用例，右侧图片对应第二个测试用例。