Bags and Coins

Description:

Input:

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₁, a₂, ..., a_n (1 ≤ a_i ≤ 70000), where a_i shows the number of coins in the i-th bag.

Output:

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.

Sample Input:

3 3
1 3 1

Sample Output:

1 0
1 2 3 1
1 0

Sample Input:

3 3
1 3 1

Sample Output:

1 0
2 1 3
0 1 1

Sample Input:

1 2
1

Sample Output:

-1

Sample Input:

8 10
2 7 3 4 1 3 1 2

Sample Output:

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

Note:

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.