Nusret Gökçe 绝对是迄今为止最昂贵的厨师之一（至少从他的顾客必须支付的账单来看是这样的）。他正在准备他的招牌菜：24K 黄金牛排（字面意思）。他烤制了一块外表焦脆、完美五分熟的牛排，并小心翼翼地将其切成 $n$ 块。正当他准备撒上一小撮盐时，意想不到的事情发生了：他的新手学徒在牛排旁绊倒了，把盐撒得满牛排都是！现在，这块原本完美的黄金牛排的每一块切片上分别有了 $s_1, s_2, \dots, s_n$ 粒盐。

Nusret 正在为他的招牌菜撒盐。来源：eater.com

Nusret 可不是一个会扔掉食物的人（特别是当这些食物贵如黄金时）；因此，他决定挽救这块牛排。在不破坏牛排质地的情况下，他无法去掉已有的盐；相反，他将利用自己高超的撒盐技巧和颗粒级的精准度，向这 $n$ 块切片中的一些切片中加入更多的盐，以使盐的分布更加均匀。

他知道顾客会按顺序食用这 $n$ 块切片，因此如果任意两个相邻切片之间的盐量相差不超过 $m$ 粒，顾客就不会察觉到任何异常。同时，他也不希望牛排变得过于咸；因此，他会以使盐的总粒数尽可能少的方式来撒盐。

在 Nusret “挽救”了他的招牌菜之后，每块切片上会有多少粒盐？

输入格式

第一行包含两个整数 $n$（$1 \le n \le 100\,000$）和 $m$（$0 \le m \le 10^9$）—— Nusret 招牌菜的切片数量，以及允许的最大咸度差异。

第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$（$1 \le s_i \le 10^9$）—— $n$ 个切片上初始的盐粒数量。

输出格式

输出 $n$ 个整数 $t_1, t_2, \dots, t_n$，表示 Nusret 挽救这道菜后，每个切片上的盐粒数量。

任何使盐粒总数尽可能小的方案都将被接受。

样例

输入样例 1

8 3
1 16 4 2 3 8 1 9

输出样例 1

13 16 13 10 7 8 6 9

输入样例 2

5 0
1 5 7 1 6

输出样例 2

7 7 7 7 7