Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Bags and Coins

time limit per test

2.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputWhen 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.

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*_{1}, *a*_{2}, ..., *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.

Examples

Input

3 3

1 3 1

Output

1 0

1 2 3 1

1 0

Input

3 3

1 3 1

Output

1 0

2 1 3

0 1 1

Input

1 2

1

Output

-1

Input

8 10

2 7 3 4 1 3 1 2

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2018 06:37:13 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|