CF1239C.Queue in the Train

There are $n$ seats in the train's car and there is exactly one passenger occupying every seat. The seats are numbered from $1$ to $n$ from left to right. The trip is long, so each passenger will become hungry at some moment of time and will go to take boiled water for his noodles. The person at seat $i$ ($1 \leq i \leq n$) will decide to go for boiled water at minute $t_i$.

Tank with a boiled water is located to the left of the $1$-st seat. In case too many passengers will go for boiled water simultaneously, they will form a queue, since there can be only one passenger using the tank at each particular moment of time. Each passenger uses the tank for exactly $p$ minutes. We assume that the time it takes passengers to go from their seat to the tank is negligibly small.

Nobody likes to stand in a queue. So when the passenger occupying the $i$-th seat wants to go for a boiled water, he will first take a look on all seats from $1$ to $i - 1$. In case at least one of those seats is empty, he assumes that those people are standing in a queue right now, so he would be better seating for the time being. However, at the very first moment he observes that all seats with numbers smaller than $i$ are busy, he will go to the tank.

There is an unspoken rule, that in case at some moment several people can go to the tank, than only the leftmost of them (that is, seating on the seat with smallest number) will go to the tank, while all others will wait for the next moment.

Your goal is to find for each passenger, when he will receive the boiled water for his noodles.

列车车厢内共有 $n$ 个座位，每个座位上恰好坐有一名乘客。座位从左到右依次编号为 $1$ 到 $n$。旅途漫长，因此每名乘客会在某个时刻感到饥饿，并起身去取开水煮面。坐在第 $i$ 个座位上的乘客（$1 \leq i \leq n$）将在第 $t_i$ 分钟决定去取开水。

盛有开水的水箱位于第 $1$ 号座位的左侧。若有多名乘客同时前往取水，则会形成队列，因为任意时刻最多只允许一名乘客使用水箱。每名乘客使用水箱的时间恰好为 $p$ 分钟。我们假设乘客从座位走到水箱所花费的时间可忽略不计。

没有人喜欢排队等候。因此，当坐在第 $i$ 号座位上的乘客想要去取开水时，他首先会观察编号为 $1$ 至 $i-1$ 的所有座位：若其中至少有一个座位是空的，他就推断这些空座位对应的乘客此刻正在排队，于是自己选择暂时先坐着等待；然而，一旦他首次发现所有编号小于 $i$ 的座位均被占用（即无人在排队），他便会立即前往水箱。

另有一条不成文的规定：若在某一时刻有多个乘客可以前往水箱（即满足前述“首次发现所有编号更小的座位均被占用”的条件），则仅最左侧者（即座位编号最小者）前去水箱，其余人继续等待下一时刻。

你的任务是：对每名乘客，求出他最终取到开水的时间（即其使用水箱结束的时刻）。

The first line contains integers $n$ and $p$ ($1 \leq n \leq 100\,000$, $1 \leq p \leq 10^9$) — the number of people and the amount of time one person uses the tank.

The second line contains $n$ integers $t_1, t_2, \dots, t_n$ ($0 \leq t_i \leq 10^9$) — the moments when the corresponding passenger will go for the boiled water.

第一行包含两个整数 $n$ 和 $p$（$1 \leq n \leq 100\,000$，$1 \leq p \leq 10^9$）—— 分别表示人数以及每人使用水箱所需的时间。

第二行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$（$0 \leq t_i \leq 10^9$）—— 表示对应乘客前往取开水的时刻。

Print $n$ integers, where $i$-th of them is the time moment the passenger on $i$-th seat will receive his boiled water.

输出 $n$ 个整数，其中第 $i$ 个整数表示坐在第 $i$ 个座位上的乘客收到开水的时间时刻。

Consider the example.

At the $0$-th minute there were two passengers willing to go for a water, passenger $1$ and $5$, so the first passenger has gone first, and returned at the $314$-th minute. At this moment the passenger $2$ was already willing to go for the water, so the passenger $2$ has gone next, and so on. In the end, $5$-th passenger was last to receive the boiled water.

考虑如下示例：

在第 $0$ 分钟时，有两位乘客（乘客 $1$ 和乘客 $5$）希望去打水，因此乘客 $1$ 先前往打水，并于第 $314$ 分钟返回。此时乘客 $2$ 已经等待打水，因此乘客 $2$ 紧接着前往打水，依此类推。最终，乘客 $5$ 是最后一位喝到开水的乘客。