G. Сбалансированное распределение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вдоль кольцевой дороги живут $$$n$$$ друзей. Друзья и их дома пронумерованы по часовой стрелке от $$$0$$$ до $$$n-1$$$.

Изначально у человека $$$i$$$ есть $$$a_i$$$ камней. Друзья хотят сделать распределение камней между ними идеально сбалансированным: у всех должно оказаться равное число камней.

Единственный способ менять распределение камней — проводить встречи. Во время встречи люди из ровно $$$k$$$ последовательных домов (помните, что дорога кольцевая) собираются в одном месте и приносят с собой все свои камни. Все принесённые камни могут быть произвольно перераспределены между пришедшими на встречу людьми. Общее число камней до встречи и после неё должно остаться тем же. После встречи все возвращаются к себе домой.

Найдите способ сделать распределение камней идеально сбалансированным, проведя как можно меньше встреч.

Входные данные

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le k < n \le 10^5$$$) — число друзей и размер одной встречи.

Вторая строка содержит $$$n$$$ целых чисел $$$a_0, a_1, \ldots, a_{n-1}$$$ ($$$0 \le a_i \le 10^4$$$) — изначальное число камней у людей.

Сумма всех $$$a_i$$$ делится на $$$n$$$.

Выходные данные

Выведите наименьшее число встреч $$$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$$$ непробельных символов.

Примеры
Входные данные
6 3
2 6 1 10 3 2
Выходные данные
3
2 7 3 4
5 4 4 2
1 4 4 4
Входные данные
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
Примечание

В первом примере распределение камней меняется следующим образом:

  • после первой встречи: $$$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}$$$.