Problem Description

There are $10^{100}$ white squares arranged in a single row. The $i$-th square from the left (for $1 \leq i \leq 10^{100}$) is called square $i$.

Additionally, there are $N$ pieces, and the $i$-th piece (for $1 \leq i \leq N$) is called piece $i$.

Furthermore, there is a counter that can count numbers from $0$ to $10^{100}$.

We will perform $N$ operations on these squares and pieces. The $i$-th operation (for $1 \leq i \leq N$) is performed as follows:

1. First, place piece $i$ on square $S_i$ and initialize the counter to $0$.
2. If the square where the piece is located is white, paint that square black and increment the counter by $1$. If the square where the piece is located is black, move the piece one square to the right.
3. Repeat step $2$ until the counter's value reaches $C_i$, at which point the operation ends.

Determine the positions of the $N$ pieces after all operations are completed.

Input Format

The input is given from the 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 \leq N \leq 10^5$).
• The next $N$ lines contain the information for each operation. The $i$-th line (for $1 \leq i \leq N$) contains integers $S_i$ ($1 \leq S_i \leq 10^9$) and $C_i$ ($1 \leq C_i \leq 10^9$), which indicate that piece $i$ is initially placed on square $S_i$ and the operation ends when the counter reaches $C_i$.

Output Format

The output consists of $N$ lines. The $i$-th line (for $1 \leq i \leq N$) should contain a single integer representing the number of the square where piece $i$ is located after all operations are completed. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

4
3 3
10 1
4 2
2 4

Sample Output #1

5
10
7
11

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

Notes/Hints

Partial Points

This problem has partial scoring:

• If the positions of all pieces after all operations are $10^5$ or less, you will receive $35$ points.
• If $N \leq 1000$, you will receive an additional $40$ points.
• If you solve the problem without additional constraints, you will receive an additional $25$ points.

Sample Explanation 1

The figure below shows the state of the squares and pieces after each operation.

Sample Explanation 3

Note that the output may exceed the 32-bit integer type.

见题面 Input 部分

见题面 Output 部分