Problem Statement

We have ~N~ bulbs arranged on a number line, numbered ~1~ to ~N~ from left to right. Bulb ~i~ is at coordinate ~i~ .

Each bulb has a non-negative integer parameter called intensity. When there is a bulb of intensity ~d~ at coordinate ~x~ , the bulb illuminates the segment from coordinate ~x-d-0.5~ to ~x+d+0.5~ . Initially, the intensity of Bulb ~i~ is ~A_i~ . We will now do the following operation ~K~ times in a row:

• For each integer ~i~ between ~1~ and ~N~ (inclusive), let ~B_i~ be the number of bulbs illuminating coordinate ~i~ . Then, change the intensity of each bulb ~i~ to ~B_i~ .

Find the intensity of each bulb after the ~K~ operations.

Constraints

• ~1 \leq N \leq 2 \times 10^5~
• ~1 \leq K \leq 2 \times 10^5~
• ~0 \leq A_i \leq N~

Input

Input is given from Standard Input in the following format:

~N~ ~K~

~A_1~ ~A_2~ ~\ldots~ ~A_N~

Output

Print the intensity ~A{'}_i~ of each bulb ~i~ after the ~K~ operations to Standard Output in the following format:

~A{'}_1~ ~A{'}_2~ ~\ldots~ ~A{'}_N~

Sample Input 1

5 1
1 0 0 1 0

Sample Output 1

1 2 2 1 2

Initially, only Bulb ~1~ illuminates coordinate ~1~ , so the intensity of Bulb ~1~ becomes ~1~ after the operation. Similarly, the bulbs initially illuminating coordinate ~2~ are Bulb ~1~ and ~2~ , so the intensity of Bulb ~2~ becomes ~2~ .

Sample Input 2

5 2
1 0 0 1 0

Sample Output 2

3 3 4 4 3