售票窗口

题目描述

AtCoder Land 的入口处有一个售票窗口，游客们排队依次买票。每人买票需要 $A$ 秒。排在队伍最前面的人买完票后，下一个人（如果有的话）会立刻开始买票。

现在售票窗口前没有人在排队，有 $N$ 个人会依次来买票。具体来说，第 $i$ 个人将在从现在起 $T_i$ 秒后到达售票窗口。如果此时已经有人在排队，他就排在队尾；如果没有人排队，他立刻开始买票。这里保证 $T_1 \lt T_2 \lt \dots \lt T_N$。

对于每个 $i\ (1 \leq i \leq N)$，求出第 $i$ 个人买完票的时刻（从现在起的秒数）。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出 $N$ 行。第 $i$ 行输出第 $i$ 个人买完票的时刻（从现在起的秒数）。

样例

3 4
0 2 10

4
8
14

事件按以下顺序进行：

• 第 $0$ 秒：第 $1$ 个人到达售票窗口，开始买票。
• 第 $2$ 秒：第 $2$ 个人到达售票窗口，排在队尾。
• 第 $4$ 秒：第 $1$ 个人买完票，第 $2$ 个人开始买票。
• 第 $8$ 秒：第 $2$ 个人买完票。
• 第 $10$ 秒：第 $3$ 个人到达售票窗口，开始买票。
• 第 $14$ 秒：第 $3$ 个人买完票。

3 3
1 4 7

4
7
10

事件按以下顺序进行：

• 第 $1$ 秒：第 $1$ 个人到达售票窗口，开始买票。
• 第 $4$ 秒：第 $1$ 个人买完票，第 $2$ 个人到达售票窗口，开始买票。
• 第 $7$ 秒：第 $2$ 个人买完票，第 $3$ 个人到达售票窗口，开始买票。
• 第 $10$ 秒：第 $3$ 个人买完票。

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

170190
220190
270190
506895
590000
640000
690000
793796
843796
1041216

数据范围

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