Problem E
Precarious Stacks

Illustration of Sample Input 4.

It’s been difficult finding a job in the tech industry lately. You managed to land a job working for a construction company, but some of the tasks being assigned to you have you wondering whether the engineers have ever heard of gravity. Anyway, in the latest task, you are asked to evaluate the following model of a construction project.

The model is built by dropping axis-aligned squares, each with a specific $x$ coordinate and size, towards the ground (which is defined by the line $y=0$). Each square will move downwards until its bottom face hits the ground or some other square. Once a square lands, it is securely fastened in place, so even if two squares are off balance, they will not fall over.

Given the list of squares to place and the order to place them in, determine the maximum $y$ coordinate reached by the structure after each square is placed.

Input

The first line of input contains an integer $N$ ($1 \le N \le 10^5$) indicating how many squares there are in the model. The next $N$ lines describe the squares in the ordered they are to be dropped. Line $i$ contains two integers $x_ i$ ($0 \le x_ i \le 10^9$) and $s_ i$ ($1 \le s_ i \le 10^9$), indicating the $x$ coordinate of the leftmost edge of square $i$ and the size of square $i$, respectively.

Output

Output $N$ lines, with line $i$ containing the $y$ coordinate of the highest point that is reached by the structure after squares $1,\dots ,i$ have been dropped.

3
0 1
0 2
0 3

1
3
6

5
0 1
0 10
9 1
0 10
9 10

1
11
12
22
32

3
0 1
1 1
2 1

1
1
1

7
0 5
1 4
2 3
3 2
4 1
0 2
0 5

5
9
12
14
15
15
20