有 $$$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$$$ 非空白字符。
示例
输入 #1
6 3 2 6 1 10 3 2
输出 #1
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
输出 #2
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$$$ $$$2$$$ $$$\mathbf{2}$$$。