Queue in the Train

题意翻译

n个人坐成一列,每个人都有一个打算喝水的时间点ti,一个人不到点是不会去喝水的。另外,饮水机在第一个人座位的左侧,也就是说如果有多人同时要去喝水,那么位置靠左的人会先起身。一个人在饮水机接水需要时间(但是走路不要时间),每个人接水消耗的时间一样。由于没人喜欢排队,所以如果一个人发现在他的前方(编号小于他)的任意一个座位空了(说明那个人正在排队),他就会在自己的座位上等待,直到所有在他前方的人都回到座位上。需要注意的一点是,如果有几个人同时打算起身,编号最靠前的会先起身,而靠后的会乖♂乖坐下。 (原题是泡面,这里直接说打开水应该没差。。) 输入: 第一行 :人数n(1<=n<=100000),每个人装水耗时p(1<=p<=1e9) 第二行 : 每个人打算喝水的时间点ti(1<=i<=n , 0<=ti<=1e9) (输入全都是整数) 输出: 一行整数,第i个数表示第i个人喝到水的时间(必须装完水才能喝)

题目描述

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.

输入输出样例

输入样例 #1

5 314
0 310 942 628 0

输出样例 #1

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.