Вдоль кольцевой дороги живут \(n\) друзей. Друзья и их дома пронумерованы по часовой стрелке от \(0\) до \(n-1\).
Изначально у человека \(i\) есть \(a_i\) камней. Друзья хотят сделать распределение камней между ними идеально сбалансированным: у всех должно оказаться равное число камней.
Единственный способ менять распределение камней — проводить встречи. Во время встречи люди из ровно \(k\) последовательных домов (помните, что дорога кольцевая) собираются в одном месте и приносят с собой все свои камни. Все принесённые камни могут быть произвольно перераспределены между пришедшими на встречу людьми. Общее число камней до встречи и после неё должно остаться тем же. После встречи все возвращаются к себе домой.
Найдите способ сделать распределение камней идеально сбалансированным, проведя как можно меньше встреч.
Выходные данные
Выведите наименьшее число встреч \(m\) (\(m \ge 0\)) и \(m\) описаний встреч в хронологическом порядке.
\(i\)-е описание должно состоять из целого числа \(s_i\) (\(0 \le s_i < n\)) и \(k\) неотрицательных целых чисел \(b_{i, 0}, b_{i, 1}, \ldots, b_{i, k-1}\) (\(b_{i, j} \ge 0\)). Такое описание обозначает встречу людей \(s_i, (s_i + 1) \bmod n, \ldots, (s_i + k - 1) \bmod n\), а \(b_{i,j}\) обозначает число камней, которое должно оказаться у человека \((s_i + j) \bmod n\) после \(i\)-й встречи. Сумма \(b_{i, j}\) должна совпадать с общим числом камней, которое было у этих людей до \(i\)-й встречи.
Можно показать, что решение существует для любого корректного ввода, а любой корректный вывод содержит не более \(10^7\) непробельных символов.
Примечание
В первом примере распределение камней меняется следующим образом:
- после первой встречи: \(2\) \(6\) \(\mathbf{7}\) \(\mathbf{3}\) \(\mathbf{4}\) \(2\);
- после второй встречи: \(\mathbf{4}\) \(\mathbf{2}\) \(7\) \(3\) \(4\) \(\mathbf{4}\);
- после третьей встречи: \(4\) \(\mathbf{4}\) \(\mathbf{4}\) \(\mathbf{4}\) \(4\) \(4\).
Во втором примере распределение камней меняется следующим образом:
- после первой встречи: \(1\) \(0\) \(1\) \(\mathbf{2}\) \(\mathbf{2}\) \(\mathbf{2}\) \(\mathbf{2}\) \(2\) \(4\) \(3\) \(3\);
- после второй встречи: \(\mathbf{5}\) \(0\) \(1\) \(2\) \(2\) \(2\) \(2\) \(2\) \(\mathbf{2}\) \(\mathbf{2}\) \(\mathbf{2}\);
- после третьей встречи: \(\mathbf{2}\) \(\mathbf{2}\) \(\mathbf{2}\) \(2\) \(2\) \(2\) \(2\) \(2\) \(2\) \(2\) \(\mathbf{2}\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3
2 6 1 10 3 2
|
3
2 7 3 4
5 4 4 2
1 4 4 4
|
|
2
|
11 4
1 0 1 0 0 4 4 2 4 3 3
|
3
3 2 2 2 2
8 2 2 2 5
10 2 2 2 2
|