Queue in the Train

$n$ 个人，编号分别为 $1\sim n$，在火车上坐成一列，第 $i$ 个人想要在时刻 $t_i$ 去饮水机接水。每个人有四种状态：坐在座位上无所事事；坐在座位上但想去饮水机；正在饮水机旁排队；正在打水。初始时，所有人都坐在座位上无所事事。注意，“正在饮水机旁排队”的所有人形成一个先进后出的队列。 每个人打水需要 $p$ 分钟。在座位和饮水机之间移动不需要时间。 按照时刻的流逝，每一时刻 $x$ **依次**发生如下事件： - 如果 $x-p$ 时刻，某个人 $j$ 恰好开始打水，则此时他停止打水，并回到座位上，进入无所事事状态。 - 如果存在 $i$ 使得 $t_i=x$，则 $i$ 的状态从“无所事事”变为“想去饮水机”。如果有多个 $i$ 满足要求，则状态都改变。 - 如果编号为 $k$ 的人目前坐在座位上但想去饮水机，且当前饮水机旁队列中所有人编号都大于 $k$，则 $k$ 就会到饮水机旁排队（站在队列末尾）。如果有多个人满足要求，只有编号 $k$ 最小的人会进入队列，其它人仍然处于“坐在座位上但想去饮水机”状态。 - 如果现在饮水机旁的队列非空，且没有人正在饮水机上打水，则队列中最靠前的人进入“正在打水”状态。 求每个人在哪个时刻打完水。

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.

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.

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

5 314
0 310 942 628 0

314 628 1256 942 1570 

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.