103581: [Atcoder]ABC358 B - Ticket Counter

Problem Statement

At the entrance of AtCoder Land, there is a single ticket booth where visitors line up to purchase tickets one by one. The purchasing process takes $A$ seconds per person. Once the person at the front of the line finishes purchasing their ticket, the next person (if any) immediately starts their purchasing process.

Currently, there is no one in line at the ticket booth, and $N$ people will come to buy tickets one after another. Specifically, the $i$-th person will arrive at the ticket booth $T_i$ seconds from now. If there is already a line, they will join the end of it; if not, they will start the purchasing process immediately. Here, $T_1 < T_2 < \dots < T_N$.

For each $i\ (1 \leq i \leq N)$, determine how many seconds from now the $i$-th person will finish purchasing their ticket.

Constraints

• $1 \leq N \leq 100$
• $0 \leq T_1 < T_2 < \dots < T_N \leq 10^6$
• $1 \leq A \leq 10^6$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $A$
$T_1$ $T_2$ \dots $T_N$

Output

Print $N$ lines. The $i$-th line should contain the number of seconds from now that the $i$-th person will finish purchasing their ticket.

Sample Input 1

3 4
0 2 10

Sample Output 1

4
8
14

The events proceed in the following order:

• At $0$ seconds: The 1st person arrives at the ticket booth and starts the purchasing process.
• At $2$ seconds: The 2nd person arrives at the ticket booth and joins the line behind the 1st person.
• At $4$ seconds: The 1st person finishes purchasing their ticket, and the 2nd person starts the purchasing process.
• At $8$ seconds: The 2nd person finishes purchasing their ticket.
• At $10$ seconds: The 3rd person arrives at the ticket booth and starts the purchasing process.
• At $14$ seconds: The 3rd person finishes purchasing their ticket.

Sample Input 2

3 3
1 4 7

Sample Output 2

4
7
10

The events proceed in the following order:

• At $1$ second: The 1st person arrives at the ticket booth and starts the purchasing process.
• At $4$ seconds: The 1st person finishes purchasing their ticket, and the 2nd person arrives at the ticket booth and starts the purchasing process.
• At $7$ seconds: The 2nd person finishes purchasing their ticket, and the 3rd person arrives at the ticket booth and starts the purchasing process.
• At $10$ seconds: The 3rd person finishes purchasing their ticket.

Sample Input 3

10 50000
120190 165111 196897 456895 540000 552614 561627 743796 757613 991216

Sample Output 3

170190
220190
270190
506895
590000
640000
690000
793796
843796
1041216

问题描述

在进入AtCoder Land的入口处，有一个售票亭，游客们会一个接一个地排队买票。每个人的购票过程需要$A$秒的时间。一旦排在队伍最前面的人买完票，下一个人（如果有的话）会立即开始购票过程。

现在售票亭前没有人排队，接下来会有$N$个人依次来买票。具体来说，第$i$个人将在$T_i$秒后到达售票亭。如果有队伍，他们会加入队伍的末尾；如果没有队伍，他们会立即开始购票。这里，$T_1 < T_2 < \dots < T_N$。

对于每个$i\ (1 \leq i \leq N)$，确定第$i$个人从现在起需要多少秒才能买完票。

约束条件

• $1 \leq N \leq 100$
• $0 \leq T_1 < T_2 < \dots < T_N \leq 10^6$
• $1 \leq A \leq 10^6$
• 所有输入值都是整数。

输入

输入通过标准输入给出，格式如下：

$N$ $A$
$T_1$ $T_2$ \dots $T_N$

输出

打印$N$行。第$i$行应包含第$i$个人从现在起完成购票需要的秒数。

样例输入1

3 4
0 2 10

样例输出1

4
8
14

事件按以下顺序进行：

• 在$0$秒：第1个人到达售票亭并开始购票过程。
• 在$2$秒：第2个人到达售票亭，加入第1个人后面排队。
• 在$4$秒：第1个人完成购票，第2个人开始购票过程。
• 在$8$秒：第2个人完成购票。
• 在$10$秒：第3个人到达售票亭并开始购票过程。
• 在$14$秒：第3个人完成购票。

样例输入2

3 3
1 4 7

样例输出2

4
7
10

事件按以下顺序进行：

• 在$1$秒：第1个人到达售票亭并开始购票过程。
• 在$4$秒：第1个人完成购票，第2个人到达售票亭并开始购票过程。
• 在$7$秒：第2个人完成购票，第3个人到达售票亭并开始购票过程。
• 在$10$秒：第3个人完成购票。

样例输入3

10 50000
120190 165111 196897 456895 540000 552614 561627 743796 757613 991216

样例输出3

170190
220190
270190
506895
590000
640000
690000
793796
843796
1041216