Наверняка, в детстве вам рассказывали загадку про мешочки и монетки. Если нет, вот один из ее вариантов:
У Коня есть три мешочка. В первом лежит одна монетка, во втором — одна монетка, а в третьем — три монетки. Всего у Коня во всех мешочках лежит три монетки. Как такое может быть?
Ответ на эту загадку очень простой. А именно, в третьем мешочке лежат первые два и одна монетка.
Данная задача — это обобщение детской загадки. Имеется n мешочков. Известно, что в первом мешочке находится a1 монет, во втором мешочке находится a2 монет, ..., в n-ом — an монет. Общее количество монет равно s. Найдите, как расположить мешочки и монетки в них таким образом, чтобы описанное выполнялось, или сообщите, что сделать это невозможно.
Выходные данные
Если ответа не существует, выведите -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 0
1 2 3 1
1 0
|
|
2
|
3 3
1 3 1
|
1 0
2 1 3
0 1 1
|
|
3
|
1 2
1
|
-1
|
|
4
|
8 10
2 7 3 4 1 3 1 2
|
2 0
1 2 1 4
0 2 7 8
0 2 5 6
1 0
3 0
1 0
2 0
|