| Codeforces Round 207 (Div. 1) |
|---|
| Закончено |
Наверняка, в детстве вам рассказывали загадку про мешочки и монетки. Если нет, вот один из ее вариантов:
У Коня есть три мешочка. В первом лежит одна монетка, во втором — одна монетка, а в третьем — три монетки. Всего у Коня во всех мешочках лежит три монетки. Как такое может быть?
Ответ на эту загадку очень простой. А именно, в третьем мешочке лежат первые два и одна монетка.
Данная задача — это обобщение детской загадки. Имеется n мешочков. Известно, что в первом мешочке находится a1 монет, во втором мешочке находится a2 монет, ..., в n-ом — an монет. Общее количество монет равно 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.
Никакой мешочек не должен лежать в более чем одном мешочке непосредственно. Допускается более одного уровня вложенности мешочков (смотрите второй тестовый пример). Если существует несколько правильных ответов, разрешается вывести любой.
3 3
1 3 1
1 0
1 2 3 1
1 0
3 3
1 3 1
1 0
2 1 3
0 1 1
1 2
1
-1
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
На рисунках снизу показаны два возможных решения одного и того же тестового примера из условия. Левый рисунок соответствует первому тестовому примеру, правый — второму тестовому примеру.
