Problem Statement

$N$ people are standing on a number line, and person $1$ is at position $0$.
The distance from person $i - 1(2 \le i \le N)$ to person $i$ is $a_i$ in the positive direction.
Due to the spread of a new virus, the distance between people must now be at least $D$ as social distancing.
Therefore, in order starting from person $2$, person $i$, if their distance from person $i-1$ is less than $D$, moves in the positive direction until the distance becomes $D$.
If this move reverses their position relative to person $i+1$, it is treated as a negative distance. In other words, to satisfy the condition, in the end person $i+1$ is always at a larger coordinate than person $i$.
Output the coordinates of all $N$ people after social distancing.

Input

$N\ D$
$a_2\ a_3\ \dots a_N$

$2 \le N \le 10^5$
$1 \le D, a_i \le 1000(=10^3)$

Output

Print the coordinates of the $N$ people on one line, separated by spaces. Do not put a trailing space. End the output with a newline.

Sample

5 2
1 2 3 1000

0 2 4 6 1006

10 90
1 2 3 4 5 6 7 8 9

0 90 180 270 360 450 540 630 720 810