C - Special Trains Editorial /

Time Limit: 3 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

Atcoder国に、 1 本の東西方向に走る鉄道が完成しました。

この鉄道には N 個の駅があり、西から順に 1,2,...,N の番号がついています。

明日、鉄道の開通式が開かれます。

この鉄道では、1≦i≦N-1 を満たす全ての整数 i に対して、駅 i から駅 i+1 に、C_i 秒で向かう列車が運行されます。ただし、これら以外の列車は運行されません。

駅 i から駅 i+1 に移動する列車のうち最初の列車は、開通式開始 S_i 秒後に駅 i を発車し、その後は F_i 秒おきに駅 i を発車する列車があります。

また、S_i は F_i で割り切れることが保証されます。

つまり、A％B で A を B で割った余りを表すとき、S_i≦t,t％F_i=0 を満たす全ての t に対してのみ、開通式開始 t 秒後に駅 i を出発し、開通式開始 t+C_i 秒後に駅 i+1 に到着する列車があります。

列車の乗り降りにかかる時間を考えないとき、全ての駅 i に対して、開通式開始時に駅 i にいる場合、駅 N に到着できるのは最も早くて開通式開始何秒後か、答えてください。

制約

  • 1≦N≦500
  • 1≦C_i≦100
  • 1≦S_i≦10^5
  • 1≦F_i≦100
  • S_i％F_i=0
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N
C_1 S_1 F_1
:
C_{N-1} S_{N-1} F_{N-1}

出力

i 行目 (1≦i≦N) に、開通式開始時に駅 i にいる場合、駅 N に到着できるのが最も早くて開通式開始 x 秒後のとき、x を出力せよ。

入力例 1

3
6 5 1
1 10 1

出力例 1

12
11
0

駅 1 からは、以下のように移動します。

  • 開通式開始 5 秒後に、駅 2 に向かう列車に乗る。
  • 開通式開始 11 秒後に、駅 2 に到着する。
  • 開通式開始 11 秒後に、駅 3 に向かう列車に乗る。
  • 開通式開始 12 秒後に、駅 3 に到着する。

駅 2 からは、以下のように移動します。

  • 開通式開始 10 秒後に、駅 3 に向かう列車に乗る。
  • 開通式開始 11 秒後に、駅 3 に到着する。

駅 3 に対しても、0 を出力しなければならないことに注意してください。

入力例 2

4
12 24 6
52 16 4
99 2 2

出力例 2

187
167
101
0

入力例 3

4
12 13 1
44 17 17
66 4096 64

出力例 3

4162
4162
4162
0

Score : 300 points

Problem Statement

A railroad running from west to east in Atcoder Kingdom is now complete.

There are N stations on the railroad, numbered 1 through N from west to east.

Tomorrow, the opening ceremony of the railroad will take place.

On this railroad, for each integer i such that 1≤i≤N-1, there will be trains that run from Station i to Station i+1 in C_i seconds. No other trains will be operated.

The first train from Station i to Station i+1 will depart Station i S_i seconds after the ceremony begins. Thereafter, there will be a train that departs Station i every F_i seconds.

Here, it is guaranteed that F_i divides S_i.

That is, for each Time t satisfying S_i≤t and t％F_i=0, there will be a train that departs Station i t seconds after the ceremony begins and arrives at Station i+1 t+C_i seconds after the ceremony begins, where A％B denotes A modulo B, and there will be no other trains.

For each i, find the earliest possible time we can reach Station N if we are at Station i when the ceremony begins, ignoring the time needed to change trains.

Constraints

  • 1≤N≤500
  • 1≤C_i≤100
  • 1≤S_i≤10^5
  • 1≤F_i≤10
  • S_i％F_i=0
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

N
C_1 S_1 F_1
:
C_{N-1} S_{N-1} F_{N-1}

Output

Print N lines. Assuming that we are at Station i (1≤i≤N) when the ceremony begins, if the earliest possible time we can reach Station N is x seconds after the ceremony begins, the i-th line should contain x.

Sample Input 1

3
6 5 1
1 10 1

Sample Output 1

12
11
0

We will travel from Station 1 as follows:

  • 5 seconds after the beginning: take the train to Station 2.
  • 11 seconds: arrive at Station 2.
  • 11 seconds: take the train to Station 3.
  • 12 seconds: arrive at Station 3.

We will travel from Station 2 as follows:

  • 10 seconds: take the train to Station 3.
  • 11 seconds: arrive at Station 3.

Note that we should print 0 for Station 3.

Sample Input 2

4
12 24 6
52 16 4
99 2 2

Sample Output 2

187
167
101
0

Sample Input 3

4
12 13 1
44 17 17
66 4096 64

Sample Output 3

4162
4162
4162
0