Racetrack

On a circular racetrack, $n$ players run a fixed number of laps. Every player has her own maximum speed. Player $i$ needs $t_i$ units of time for one lap at maximum speed and has to complete $c_i$ laps.

On this track a player can pass another player only at the finish line. When a player catches up with a slower player during a lap, she stays right behind him until the end of that lap, so the two cross the finish line at the same moment.

Every player who crosses the finish line at the same moment starts again from there at her own maximum speed, so faster players move ahead of slower ones.

At the start all players stand together at the finish line. A player who completes her last lap leaves the track at once and blocks nobody after that.

Given the lap time and the number of laps of every player, compute the moment each player completes the race.

The first line contains the number of players $n$ ($1 \le n \le 5000$).

Each of the next $n$ lines describes one player: the $i$-th of them contains the lap time $t_i$ and the number of laps $c_i$ of player $i$ ($1 \le t_i \le 10^6$, $1 \le c_i \le 1000$).

The players are given in order of decreasing speed, that is $t_1 \le t_2 \le \dots \le t_n$.

Print $n$ lines. The $i$-th line contains the moment player $i$ completes the race.