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 $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