火车车厢内有 $$$n$$$ 个座位,并且每个座位上正好有一名乘客。座位从左到右编号为 $$$1$$$ 至 $$$n$$$。旅途时间较长,每个乘客都会在某个时候饿了,就会去拿开水泡面。座位 $$$i$$$ ($$$1 \leq i \leq n$$$) 将决定在 $$$t_i$$$ 分钟去喝开水。
装有开水的水箱位于 $$$1$$$-st 座位的左侧。如果太多乘客同时去喝开水,他们就会排队,因为在每个特定时刻只能有一名乘客使用水箱。每位乘客使用油箱的时间恰好为 $$$p$$$ 分钟。我们假设乘客从座位到油箱所需的时间非常短,可以忽略不计。
没有人喜欢排队。所以当第$$$i$$$个座位的乘客想去喝开水时,他会先看一下从$$$1$$$到$$$i - 1$$$的所有座位。如果其中至少有一个座位是空的,他就会认为这些人现在正在排队,所以他暂时会坐得更好。然而,当他第一时间发现所有编号小于 $$$i$$$ 的座位都忙时,他就会走向坦克。
有一个不成文的规则,如果某个时刻有几个人可以去坦克,那么只有最左边的人(即坐在人数最少的座位上)会去坦克,而其他人都会等待下一刻。
你的目标是找到每位乘客何时会收到煮面条的开水。
输入
第一行包含整数 $$$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$$$) — 相应乘客去喝开水的时刻。
输出
打印$$$n$$$个整数,其中第$$$i$$$个是第$$$i$$$个座位上的乘客收到开水的时刻。
示例
输入 #1
5 314 0 310 942 628 0
输出 #1
314 628 1256 942 1570
注意
考虑这个例子。
第$$$0$$$分钟有两名乘客愿意去喝水,分别是$$$1$$$和$$$5$$$,所以第一位乘客先走了,并在第$$$314$$$分钟返回。此时乘客$$$2$$$已经愿意去喝水了,所以乘客$$$2$$$已经下一个去了,以此类推。最后,第$$$5$$$乘客最后拿到了开水。