410798: GYM104114 N Nusret Gökçe

Nusret Gökçe is, by all means, one of the most valuable chefs to this date (at least, judging by the bills his customers have to pay). He is preparing his signature dish: the 24-karat gold steak (literally). He cooked the perfect medium rare steak with a shiny crust, cut it tenderly into $$$n$$$ pieces, and was about to sprinkle just a pinch of salt, when the unthinkable happened: his novice apprentice tripped next to the steak, spreading salt wildly throughout the steak pieces! Now, the otherwise perfect gold steak has $$$s_1, s_2, \ldots, s_n$$$ grains of salt, respectively on each of the slices.

Nusret nourishing his signature dish. Source: eater.com

Nusret isn't the one to throw away dishes (especially when they are worth their weight in gold); therefore, he decided to fix the steak instead. He cannot remove the existing salt without compromising the texture of the steak; instead, he will use his salt sprinkling skills and grain-level precision to add more salt to some of the $$$n$$$ slices in order to make the salt distribution more uniform.

He knows that the customer will eat the $$$n$$$ slices in order, and so they will not sense anything suspicious if the amount of salt between every two adjacent slices does not differ by more than $$$m$$$ grains. At the same time, he doesn't want to make the steak unnecessarily salty; therefore, he will sprinkle the salt in such a way that the total number of grains of salt is as small as possible.

How many grains of salt will be on each slice after Nusret "fixes" his signature dish?

The first line of the input contains two integers $$$n$$$ ($$$1 \leq n \leq 100\:000$$$) and $$$m$$$ ($$$0 \leq m \leq 10^9$$$)  — the number of slices in Nusret's signature dish, and the maximum allowed difference in saltiness.

The second line of the input contains $$$n$$$ integers $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \leq s_i \leq 10^9$$$)  — the number of grains of salt on each of the $$$n$$$ slices.

Output $$$n$$$ integers $$$t_1, t_2, \ldots, t_n$$$, representing the number of grains of salt on each of the $$$n$$$ slices after Nusret fixes the dish.

Any solution in which the total number of grains of salt is as small as possible will be accepted.

8 3
1 16 4 2 3 8 1 9

13 16 13 10 7 8 6 9 

5 0
1 5 7 1 6

7 7 7 7 7