C. Congklak
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
A typical Congklak game board.
Alice and Bill really enjoy playing board games, and they are always looking for new challenges. Recently, they discovered the Indonesian game Congklak which is played with a game board made up of several holes containing some number of stones. After playing some games, Alice quickly got the hang of it and won every game, so Bill did not want to play any more. Instead, inspired by the rules of the game, he came up with the following challenge for Alice:

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.

Examples
Input
7 1
1 3 2 0 1 0 5
Output
0 4 0 1 2 1 5
Input
4 4
1000000000000 1 2 3
Output
1 3 0 5
Note

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

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

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]$$$