Flight Delays

Alyona is leaving on a long-awaited vacation. She is so afraid of missing her flight that she arrived at the airport at time $0$. The departure board shows $n$ flights. Flight number $i$ (numbered from 1) must depart at time $t_i$, and $t_i > t_{i-1}$ for all $i \geq 2$.

Unpredictable weather in city N has just brought heavy snow to the airport area. For safety, airport staff must clear snow from the runway after each flight departs, so the departure times of any two consecutive flights must differ by at least $k$.

Alyona knows that flights depart in increasing order of their numbers. Each flight departs as early as possible, but no earlier than $k$ after the previous flight departs and no earlier than its scheduled time $t_i$.

Alyona's mind is already on her vacation, so the task of finding the actual departure time of each flight falls to you. Flight 1 has no predecessor, so its runway does not need to be cleared.

The first line contains two integers $n$ and $k$ ($1 \leq n \leq 100\,000$, $1 \leq k \leq 10^9$), the number of flights waiting to depart and the minimum gap between the departure times of two consecutive flights needed for runway clearing.

The second line contains integers $t_1, t_2, \ldots, t_n$ ($1 \leq t_1 < t_2 < \ldots < t_n \leq 10^{18}$), the scheduled departure times.

Print $n$ integers. The $i$-th integer is the actual departure time of flight $i$.

Look at the first example from the statement.

1. The first flight departs on schedule.
2. The second flight is delayed because the runway must be cleared.
3. The planned gap between the third and second flights is enough for the third flight to leave on time, despite the second flight's delay and the clearing.
4. The fourth flight departs on time.
5. The fifth flight must be delayed, because the planned gap between it and the fourth flight was not large enough.
6. The planned gap between the fifth and sixth flights was enough for clearing, but since the fifth flight was delayed, the sixth flight also departs late.