题目描述

窗外是锣鼓喧天，散发着新年的气息，@zls_XICK 列完了串门对象的名单，正准备出发，突然传来了咚咚咚的敲门声，@zls_XICK 猛地一惊，攥紧了钱包。

看到他们都带着礼物，@zls_XICK 放心地打开了门，有 $N$ 位好友前来拜访，带来了 $N$ 个礼物，这些礼物环状排列，首尾相接。这些礼物都具有一定的祝福值，第 $i$ 个礼物的祝福值为 $a_i$，而且礼物越多，@zls_XICK 就越开心，每个礼物给他带来的祝福值也就越多，第 $i$ 个礼物实际给他带来的祝福值 $a'_i$ 为这个礼物本身的祝福值和其左右共 $K$ 个礼物祝福值之和的最大值。

形式化地：

• 有整数 $L$、$R$ 满足 $L+R=K$，$L$ 表示礼物左侧所被累加的礼物数，$R$ 则为其右侧被累加的礼物数，其中 $L,R \in \left[ 0, K \right]$。

• 则 $a'_i =\max \sum\limits_{j=i-L}^{i+R}a_j$。

• 注意考虑环状累加形式。

输入格式

输入包括两行。

第一行两个整数 $N$、$K$，含义如题意。

第二行包括 $N$ 个整数，第 $i$ 个整数表示第 $i$ 个礼物的祝福值 $a_i$。

输出格式

输出一行 $N$ 个整数，第 $i$ 个整数表示第 $i$ 个礼物实际带来的祝福值 $a'_i$，每两个整数间用一个单元符空格隔开。

6 2
1 1 4 5 1 4

6 10 10 10 10 10 

数据规模与约定

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

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

对于 $100\%$ 的数据满足 $1 \le K < N \le 10^6$，$a_i \in \left[ 1, 10^9 \right]$。