题目描述

某国新建成了一条铁路, 铁路沿东西方向, 沿线共有N站, 从西到东依次编号为1,2,⋯,N

明天铁路将进行通车式, 所有列车都是从西向东运行, 并且只在相邻的站点之间有列车运行, 从第i站到第i+1站的列车全程需要花费Ci秒.

第i站出发开往第i+1站的第一班列车在通车式开始后Si秒发车, 之后每过Fi秒发出一班列车(保证Si一定是Fi的倍数)

如果不计换乘的时间, 请计算从第i站出发的乘客到达最后的第N站的时刻, 最早可能在通车式开始后多少秒.

输入格式

第一行一个正整数N

接下来N−1行, 每行三个正整数Ci,Si,Fi

输出格式

输出N行, 第i行输出从第i站出发的乘客到达第N站的最早时间.

输入样例 #1

3
6 5 1
1 10 2

输出样例 #1

13
11
0

输入样例 #2

1

输出样例 #2

0

输入样例 #3

4
1 10 10
10 0 3
5 0 4

输出样例 #3

29
17
5
0

提示

【说明提示】

从第1站出发的乘客旅行过程如下:

第5秒登上列车前往第2站, 第11秒到达, 但是从2到3的列车从第10秒开始每2秒发车一次, 需要等到第12秒登上列车前往第3站, 第13秒到达

从第2站出发的乘客旅行过程如下:

第10秒登上列车前往第3站, 第11秒到达

对于从第3站出发的乘客也要输出一个0

数据范围与约定

1≤N≤500

1≤Ci≤100

1≤Si≤105

1≤Fi≤100

保证Si一定是Fi的倍数