Problem Statement

$10^{100}$ squares are arranged in a row. The squares are numbered $1$ through $10^{100}$ from left to right.

We have $N$ pieces numbered $1$ through $N,$ and a counter that can store an integer between $0$ and $10^{100},$ inclusive.

We will perform $N$ processes using these tools. Initially, the squares are painted white. The $i^{th} (1≦i≦N)$ process is as follows:

1. Place piece $i$ on square $S_i$, and set the counter to $0$.
2. Look at the color of the square where piece $i$ is placed. If the square is white, paint it black and increment the counter by $1$. Otherwise (if the square is black), move piece $i$ one square right. As a result, a square may contain multiple pieces.
3. Terminate the process if the value of the counter is $C_i.$ Otherwise, go back to step $2.$

Find the final position of each of the $N$ pieces after all the $N$ processes.

Input

Input is given from Standard Input in the following format:

$N$ $S_1$ $C_1$ $S_2$ $C_2$ : $S_N$ $C_N$

• The first line contains an integer $N (1 ≦ N ≦ 10^5).$
• The following $N$ lines describe the processes. The $i^{th} (1 ≦ i ≦ N)$ of them contains two space-separated integers $S_i (1 ≦ S_i ≦ 10^9)$ and $C_i (1≦C_i≦10^9),$ denoting the initial position of piece $i$ in the $i^{th}$ process and the termination condition of the $i^{th}$ process, respectively.

Partial Points

Partial points may be awarded in this problem:

• $35$ points will be awarded for passing the test set satisfying the following: The number of the square where each piece is located after all the processes does not exceed $10^5$.
• Another $40$ points will be awarded for passing the test set satisfying $N ≦ 1000.$
• Another $25$ points will be awarded for passing the test set without additional constraints.

Output

Print $N$ lines, the $i^{th} (1≦i≦N)$ of which should contain the number of the square where the piece $i$ is located after all the $N$ processes. Be sure to print a newline at the end of output.

Sample Input 1

4
3 3
10 1
4 2
2 4

Sample Output 1

5
10
7
11

Illustrated below is the state of the squares and the pieces after each process:

Sample Input 2

8
2 1
3 1
1 1
5 1
1 1
9 1
8 2
7 9

Sample Output 2

2
3
1
5
4
9
10
18

Sample Input 3

5
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

Sample Output 3

1999999999
2999999999
3999999999
4999999999
5999999999

Beware that the correct output may not fit into a $32$-bit integer.