题目描述

迎新春，伴随的是欢乐与美满，所以这道题非常简单，以祝所有的 OIer 在新的一年各种赛事里 rp++。（新年礼物Ⅰ为本题的弱化版）

新年必不可少的是串门送礼，@zls_XICK 收到了来自 $N$ 位朋友的 $N$ 个礼物，每个礼物都会给他带来祝福，第 $i$ 个礼物的祝福值为 $a_i$，这些礼物排成环状，也就是第 $1$ 个礼物与第 $N$ 个礼物相接，礼物似乎蕴含着一些魔力，它们摆放在一起时祝福值会累加，累加的规则如下：

所有礼物都会累加其左右各 $K$ 个礼物的祝福值，这些礼物累加祝福值是同时的，也就是不存在一个礼物先累加后另一个礼物才累加。

形式化地：即第 $i$ 个礼物累加后的祝福值：

• $a'_i= \sum\limits_{i=i-K}^{i+K}a_i$。
• 且由于礼物环状排列，需考虑环状累加形式。

现在 @zls_XICK 想知道这些礼物祝福值累加后的祝福值 $a'_i$ 分别是多少。

输入格式

输入包括两行。

第一行输入两个整数 $N$、$K$ 分别表示礼物个数和累加祝福值的宽度。

第二行输入 $N$ 个整数表示第 $1$ ~ $N$ 个礼物的祝福值 $a_1$ ~ $a_N$。

输出格式

输出一行 $N$ 个整数。

第 $i$ 个整数表示第 $i$ 个礼物累加后的祝福值 $a'_i$，每两个整数间用空格隔开。

7 2
1 2 3 4 5 6 7

19 17 15 20 25 23 21

数据规模与约定

对于 $20\%$ 的数据满足 $1 \le N,K \le 10^3$。

对于另外 $10\%$ 的数据满足 $K=1$。

对于 $100\%$ 的数据满足 $1 \le K+1 \le \dfrac{N}{2} \le N \le 10^6,1 \le a_i \le 10^7$。