/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
AtCoder Land の入り口には 1 つのチケット売り場があり、来園客はこのチケット売り場の前に一列に並んで順にチケットを購入します。 チケットの購入手続きには一人当たり 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\ (1\leq i \leq N) 行目には、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
Score : 200 points
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