Problem L
Congklak

A typical Congklak game board.
CC BY-SA 4.0 by rikadiani17 on Pixabay

There is a game board with $n$ holes arranged in a long row. These holes are numbered from $1$ to $n$ from left to right. Initially the $i$th hole contains $a_i$ stones. Note that this setup differs from the usual Congklak game, where the game board consists of two rows and one large hole at each end.

Now Bill will play $t$ games where each game goes as follows:

Bill starts the game at the first hole, holding one new stone in his hand. He then moves along the game board from hole $1$ to hole $n$. At each hole $i$, he first checks how many stones are currently in the hole, and depending on the result he performs exactly one of the following two actions:

• If the hole is empty, he drops one stone into it. Next, he checks how many stones are still in his hand. If his hand is empty, the game stops. Otherwise, he moves his hand to hole $i+1$ next and repeats the steps.

• If there is at least one stone in the hole, he also drops one stone into it. Next, he checks how many stones are still in his hand. If his hand is empty, he takes out all the stones from hole $i$ into his hand. Regardless of whether or not his hand was empty, he moves his hand to hole $i+1$ next and repeats the steps.

When Bill moves his hand past hole $n$, the game stops and Bill discards any stones that he still holds in his hand.

Bill challenges Alice to predict in advance the number of stones in every hole after playing exactly $t$ games. Note that the game board is not reset after playing a game, i.e. the initial configuration of the second game is the same as the configuration when the first game ends.

Input

The input consists of:

• One line with two integers $n$ and $t$ ($1 \leq n \leq 10^5$, $1 \leq t \leq 10^{12}$), the number of holes and the number of games.

• One line with $n$ integers $a_1, \ldots , a_n$ ($0 \leq a_i \leq 10^{12}$), where $a_i$ describes the initial number of stones in the $i$th hole.

Output

Output $n$ integers, the $i$th of which is the number of stones in hole $i$ after playing $t$ games.

Notes

In the first sample, Bill plays exactly one game. The figure below visualizes the steps performed during this game.

In the second sample, the initial number of stones per hole is $[1000000000000, 1, 2, 3]$. The number of stones per hole after each game is:

1. $[0, 2, 3, 4]$

2. $[1, 2, 3, 4]$

3. $[0, 3, 0, 5]$

4. $[1, 3, 0, 5]$

Figure 1: Visualization of the only game which Bill plays in the first sample.
Hand icon: MIT Licence by jtblabs on svgrepo

7 1
1 3 2 0 1 0 5

0 4 0 1 2 1 5

4 4
1000000000000 1 2 3

1 3 0 5