题目描述

Atcoder 国新建成了东西向铁路，沿线共有 $N$ 个站点，从西到东依次编号为 $1, 2, \dots, N$。

所有列车仅向东行驶，仅在相邻站点间运行：从第 $i$ 站到第 $i+1$ 站的行驶全程需要花费 $C_i$ 秒。

第 $i$ 站出发开往第 $i+1$ 站的列车，首班车在通车开始后 $S_i$ 秒发车，之后每隔 $F_i$ 秒发出一班（题目保证 $S_i$ 一定是 $F_i$ 的倍数）。

忽略换乘消耗的时间，请计算：从第 $i$ 站出发的乘客，到达终点站第 $N$ 站的最早时刻（即通车开始后经过的最少秒数），输出每个 $i$ 对应的结果。

输入格式

第一行一个正整数 $N$。

接下来 $N-1$ 行，第 $i$ 行包含三个正整数 $C_i, S_i, F_i$，对应第 $i$ 段相邻区间的运行参数。

输出格式

输出共 $N$ 行，第 $i$ 行输出一个整数，表示从第 $i$ 站出发到达第 $N$ 站的最早时间。

显然从第 $N$ 站出发不需要移动，第 $N$ 行固定输出 $0$。

3
6 5 1
1 10 2

13
11
0

【说明提示】 从第1站出发的乘客旅行过程如下: 第5秒登上列车前往第2站, 第11秒到达, 但是从2到3的列车从第10秒开始每2秒发车一次, 需要等到第12秒登上列车前往第3站, 第13秒到达 从第2站出发的乘客旅行过程如下: 第10秒登上列车前往第3站, 第11秒到达 对于从第3站出发的乘客也要输出一个0

数据规模与约定

对于 $100\%$ 的数据：

$1 \le N \le 500$

$1 \le C_i \le 100$

$1 \le S_i \le 10^5$

$1 \le F_i \le 100$

保证 $S_i$ 是 $F_i$ 的正整数倍。

子任务 $1$（$30$ 分）：$N \le 100$。

子任务 $2$（$30$ 分）：$F_i = 1$。

子任务 $3$（$40$ 分）：没有特殊限制。