Problem G
Racetrack

There is a racetrack where $n$ players complete laps. Each player has their own maximum speed. In this racetrack, overtaking is only possible near the finish line at every lap: when a player approaches a slower player, she will stay behind him until at the finish line. At the finish line, all players crossing the line at the same time resume driving at their maximum speed (so faster players overtake slower ones). Initially, all players start at the finish line. Given the lap time and the number of laps to complete for each player, calculate the times they complete the race in.

Input

The first line contains an integer $n$ ($1 \leq n \leq 5\, 000$), the number of players. The following $n$ lines contain the players’ lap time and number of laps to complete: the $i$-th line contains two integers $t_ i$ and $c_ i$ ($1 \leq t_ i \leq 10^6$, $1 \leq c_ i \leq 1\, 000$), the lap time and the number of laps to complete for player $i$. The players are sorted in decreasing order of speed, that is, $t_1 \leq t_2 \leq \ldots \leq t_ n$.

Output

Output $n$ lines; the $i$’th line must contain the time that player $i$ completes the race.

Sample Input 1	Sample Output 1
2 4 8 7 6	36 42