[ABC084C] Special Trains

### 题面翻译 在AtCoder国里，明天将会举行一场铁路开通仪式。 在这条铁路上，从左往右依次有n个车站。我们不妨依次编号为1，2，3，······，n。 在这条铁路上，对于满足 1≤i≤n-1 的所有整数 i ，从车站 i 到车站 i+1 ，以 c[i] 秒运行列车。同时，这些列车以外的列车不运行。 从站 i 移动到站 i+1 的列车中的第一列列车，在开通仪式上将在开始 s[i] 秒后从站i出发，然后隔 f[i] 秒从站I I出发的shan列车。之后有每隔 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 的火车将在开始通车式几秒后。 ------------ ### 输入与输出: 输入第一行只有一个数 N ,接下来将会有 N-1 行,分别有三个数字,依次表示 c[i] , s[i] , f[i] 。 1≦N≦500 1≦c[i]≦100 1≦s[i]≦100,000 1≦f[i]≦100 输出 N-1 行，依次表示所对应数据的答案，最后输出个 0 表示输出结束。 #### 温馨提示：岛国题目最后输出完也要再换个行！ ------------

[problemUrl]: https://atcoder.jp/contests/abc084/tasks/abc084_c 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 $ に到着できるのは最も早くて開通式開始何秒後か、答えてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ C_1 $ $ S_1 $ $ F_1 $ $ : $ $ C_{N-1} $ $ S_{N-1} $ $ F_{N-1} $

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

3
6 5 1
1 10 1

12
11
0

4
12 24 6
52 16 4
99 2 2

187
167
101
0

4
12 13 1
44 17 17
66 4096 64

4162
4162
4162
0

### 制約 - $ 1≦N≦500 $ - $ 1≦C_i≦100 $ - $ 1≦S_i≦10^5 $ - $ 1≦F_i≦100 $ - $ S_i％F_i=0 $ - 入力は全て整数 ### Sample Explanation 1 駅 $ 1 $ からは、以下のように移動します。 - 開通式開始 $ 5 $ 秒後に、駅 $ 2 $ に向かう列車に乗る。 - 開通式開始 $ 11 $ 秒後に、駅 $ 2 $ に到着する。 - 開通式開始 $ 11 $ 秒後に、駅 $ 3 $ に向かう列車に乗る。 - 開通式開始 $ 12 $ 秒後に、駅 $ 3 $ に到着する。 駅 $ 2 $ からは、以下のように移動します。 - 開通式開始 $ 10 $ 秒後に、駅 $ 3 $ に向かう列車に乗る。 - 開通式開始 $ 11 $ 秒後に、駅 $ 3 $ に到着する。 駅 $ 3 $ に対しても、$ 0 $ を出力しなければならないことに注意してください。