Problem Statement

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

There are $\mathrm{NN}$ stations on the railroad, numbered $11$ through $\mathrm{NN}$ from west to east.

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

On this railroad, for each integer $\mathrm{ii}$ such that $\mathrm{1\le i\le N-11\le i\le N-1}$, there will be trains that run from Station $\mathrm{ii}$ to Station $\mathrm{i+1i+1}$ in ${\mathrm{CiCi}}^{}$ seconds. No other trains will be operated.

The first train from Station $\mathrm{ii}$ to Station $\mathrm{i+1i+1}$ will depart Station $\mathrm{ii}$ ${\mathrm{SiSi}}^{}$ seconds after the ceremony begins. Thereafter, there will be a train that departs Station $\mathrm{ii}$ every ${\mathrm{FiFi}}^{}$ seconds.

Here, it is guaranteed that ${\mathrm{FiFi}}^{}$ divides ${\mathrm{SiSi}}^{}$.

That is, for each Time $\mathrm{tt}$ satisfying ${\mathrm{Si\le tSi\le t}}^{}$ and $\mathrm{t％Fi=0t％Fi=0}$, there will be a train that departs Station $\mathrm{ii}$ $\mathrm{tt}$ seconds after the ceremony begins and arrives at Station $\mathrm{i+1i+1}$ $\mathrm{t+Cit+Ci}$ seconds after the ceremony begins, where $\mathrm{A％BA％B}$ denotes $\mathrm{AA}$ modulo $\mathrm{BB}$, and there will be no other trains.

For each $\mathrm{ii}$, find the earliest possible time we can reach Station $\mathrm{NN}$ if we are at Station $\mathrm{ii}$ when the ceremony begins, ignoring the time needed to change trains.

Constraints

• $\mathrm{1\le N\le 5001\le N\le 500}$
• $\mathrm{1\le Ci\le 1001\le Ci\le 100}$
• $\mathrm{1\le Si\le 1051\le Si\le 105}$
• $\mathrm{1\le Fi\le 101\le Fi\le 10}$
• ${\mathrm{Si％Fi=0Si％Fi=0}}^{}$
• All input values are integers.

---

Input

Input is given from Standard Input in the following format:

NN C1C1  S1S1  F1F1 :: CN−1CN−1  SN−1SN−1  FN−1FN−1

Output

Print $\mathrm{NN}$ lines. Assuming that we are at Station $\mathrm{ii}$ $(1\le i\le N)(1\le i\le N)$ when the ceremony begins, if the earliest possible time we can reach Station $\mathrm{NN}$ is $\mathrm{xx}$ seconds after the ceremony begins, the $\mathrm{ii}$-th line should contain $\mathrm{xx}$.

---

Sample Input 1 Copy

Copy

36 5 11 10 1

Sample Output 1 Copy

Copy

12110

We will travel from Station $11$ as follows:

• $55$ seconds after the beginning: take the train to Station $22$.
• $1111$ seconds: arrive at Station $22$.
• $1111$ seconds: take the train to Station $33$.
• $1212$ seconds: arrive at Station $33$.

We will travel from Station $22$ as follows:

• $1010$ seconds: take the train to Station $33$.
• $1111$ seconds: arrive at Station $33$.

Note that we should print $00$ for Station $33$.

---

Sample Input 2 Copy

Copy

412 24 652 16 499 2 2

Sample Output 2 Copy

Copy

1871671010

---

Sample Input 3 Copy

Copy

412 13 144 17 1766 4096 64

Sample Output 3 Copy

Copy

4162416241620

Fisrt,considering when it is possible to ride a train which goes to station j+1 ,in the situation that arriving station j ,t seconds after the ceremony begin.

・If t < Sj , Sj seconds after the ceremony begin.

・If t ≧ Sj ,but t ％ Fj = 0 , t seconds after the ceremony begin.

・Othersise, t + Fj −(t ％ Fj) seconds after the ceremony begin. Considering this,simulate in every case,it would be O(N2) and you can get 300 points.、

 

1 #include 
      
        2 int N,C[500],S[500],F[500]; 3 int main() 4 { 5     scanf("%d",&N); 6     for(int i=0; i