В Школе Деда Ахмеда обучается \(n+1\) ученик. Ученики разбиты на \(k\) классов, и в \(i\)-м классе обучается \(s_i\) учеников. Таким образом, \(s_1 + s_2 + \ldots + s_k = n+1\).
В честь скорого Дня дурака все ученики получат подарки!
Дед Ахмед планировал заказать \(n+1\) коробку с подарками. В каждой коробке будет один или несколько подарков. Дед Ахмед распределит их между классами так, чтобы были выполнены следующие условия:
- Класс номер \(i\) должен получить ровно \(s_i\) коробок (чтобы каждый ученик мог открыть ровно одну коробку с подарками).
- Суммарное количество подарков в коробках, полученных \(i\)-м классом, должно быть кратным \(s_i\) (то есть поровну распределяться между \(s_i\) учениками этого класса).
К сожалению, Дед Ахмед по невнимательности заказал всего \(n\) коробок с подарками, в \(i\)-й из которых содержится \(a_i\) подарков.
У Ахмеда есть время, чтобы купить недостающую коробку с подарками, причем количество подарков в коробке должно быть целым числом от \(1\) до \(10^6\). Помогите Ахмеду определить, коробку с каким количеством подарков ему стоит купить, а также постройте подходящее распределение коробок по классам, или сообщите, что это невозможно.
Выходные данные
Если подходящего распределения не существует, в единственной строке выведите число \(-1\).
Иначе, в первой строке выведите единственное число \(s\) — количество подарков в коробке, которую должен купить Дед Ахмед (\(1 \le s \le 10^6\)).
Далее в \(k\) строках выведите распределение коробок по классам. В \(i\)-й строке выведите \(s_i\) целых чисел — размеры коробок, которые попадут в \(i\)-й класс.
Если существует несколько решений, выведите любое из них.
Примечание
В первом тестовом примере Дед Ахмед может купить всего \(1\) подарок. После определить в первый класс две коробки с \(7\) подарками. \(7 + 7 = 14\) нацело делится на \(2\). А во второй класс достанутся коробки с \(1, 7, 127\) подарками. \(1 + 7 + 127 = 135\) нацело делится на \(3\).
Во втором тестовом примере классы имеют размеры \(6\), \(1\), \(9\) и \(3\). Покажем, что имеющихся коробок достаточно, чтобы распределить в классы размеров \(6\), \(9\), \(3\), а в класс размера \(1\) можно купить коробку любого размера. В класс размера \(6\) отправим коробки размеров \(7\), \(1\), \(7\), \(6\), \(5\), \(4\). \(7 + 1 + 7 + 6 + 5 + 4 = 30\) нацело делится на \(6\). В класс размера \(9\) отправим коробки размеров \(1\), \(2\), \(3\), \(8\), \(3\), \(2\), \(9\), \(8\), \(9\). \(1 + 2 + 3 + 8 + 3 + 2 + 9 + 8 + 9 = 45\) нацело делится на \(9\). В класс размера \(3\) отправятся оставшиеся коробки размеров \(6\), \(5\), \(4\). \(6 + 5 + 4 = 15\) нацело делится на \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
7 7 7 127
2 3
|
1
7 7
7 127 1
|
|
2
|
18 4
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
6 1 9 3
|
9
7 1 7 6 5 4
9
1 2 3 8 3 2 9 8 9
6 5 4
|