You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

小红拿到了一个数组，她每次可以进行以下操作： 选择两个相邻的元素，使得其中一个加1，另一个减1。

每次操作后，必须保证数组所有元素均为非负整数。

小红希望你求出以下问题，对于$i∈[1,n]$，当操作次数不超过$k$次时，使得$a_i$尽可能大，请你求出这个最大值。

请注意，每次询问均为独立的，即每次的初始数组是相同的，操作次数均为$k$。

Format

Input

第一行输入两个正整数$n$和$k$，代表数组长度和操作次数。

第二行输入$n$个整数$a_i$，代表小红拿到的数组。

Output

一行输入$n$个整数，第$i$个整数代表第$i$次询问的答案（即$k$次操作后最大化$a_i$的值）。

Samples

5 5
3 0 1 2 0

5 4 4 4 3

Limitation

$1\leq n \leq 10^5$

$1\leq k \leq 10^{14}$

$0\leq a_i \leq 10^9$

Explanation

对于$i=1$，我们首先进行一次$a_4$减1，$a_3$加1，数组变成[3,0,2,1,0]

然后进行两次$a_3$减1，$a_2$加1，数组变成[3,2,0,1,0]

然后进行两次$a_2$减1，$a_1$加1，数组变成[5,0,0,1,0]

经过5次操作，$a_1$变成了5。可以证明，这种方案是$a_1$能得到的最大值。

对于$i∈[2,5]$，不再赘述。