题目描述

AtCoder王国有一条从西向东延伸的铁路已经建成。

在铁路上有$N$个车站，编号从$1$到$N$，从西向东递增。

明天，将举行铁路的开通仪式。

在这条铁路上，对于每个满足$1 \leq i \leq N-1$的整数$i$，会有列车从第$i$个车站到第$i+1$个车站以$C_i$秒的速度运行。不会有其他列车运行。

第一辆从第$i$个车站到第$i+1$个车站的列车将在仪式开始$S_i$秒后发出。此后，每隔$F_i$秒都会有一辆从第$i$个车站发出的列车。

此处保证$F_i$可以整除$S_i$。

换句话说，对于每个满足$S_i \leq t$和$t \% F_i = 0$的时间$t$，会有一辆在仪式开始$t$秒后从第$i$个车站发出，在仪式开始$t$秒后到达第$i+1$个车站的列车，其中$A \% B$表示$A$模$B$的结果，并且没有其他列车。

对于每个$i$，找出当仪式开始时我们身处第$i$个车站时，能够到达第$N$个车站的最早时间，忽略换乘所需的时间。

约束条件

• $1 \leq N \leq 500$
• $1 \leq C_i \leq 100$
• $1 \leq S_i \leq 10^5$
• $1 \leq F_i \leq 10$
• $S_i \% F_i = 0$
• 所有输入值均为整数。

输入

从标准输入中以以下格式给出输入：

$N$ $C_1$ $S_1$ $F_1$ $\vdots$ $C_{N-1}$ $S_{N-1}$ $F_{N-1}$

输出

打印$N$行。假设我们在仪式开始时位于第$i$个车站$(1 \leq i \leq N)$，如果我们能够到达第$N$个车站的最早时间为$x$，则第$i$行应包含$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