CF1239C Queue in the Train

火车车厢内有 $n$ 个座位，每个座位上正好有一名乘客。座位从左到右编号为 $1$ 到 $n$。旅途很长，因此每位乘客在某一时刻都会感到饥饿，并前往取开水泡面。第 $i$ 个座位上的乘客会在第 $t_i$ 分钟决定去取开水。 开水箱位于第 $1$ 号座位的左侧。如果有多名乘客同时去取开水，他们会排队，因为每次只能有一人使用开水箱。每位乘客使用开水箱的时间恰好为 $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$ 个座位上的乘客拿到开水的时刻。

请参考示例。 在第 $0$ 分钟时，有两位乘客想去取开水，分别是第 $1$ 位和第 $5$ 位，因此第 $1$ 位乘客先去，并在第 $314$ 分钟返回。此时第 $2$ 位乘客已经想去取开水，因此第 $2$ 位乘客接着去，以此类推。最终，第 $5$ 位乘客最后拿到开水。 由 ChatGPT 4.1 翻译