Precarious Stacks

Time limit4sMemory limit1024 MB

Summary

Given N squares dropped in order, each landing on the ground or on earlier squares, report the highest y coordinate after each drop.

Level: Medium5 of 10
Topics: Segment tree, Sorting
Solved: No attempts yet

Problem

It has been difficult to find a job in the tech industry lately. You landed a job at a construction company, but some of the tasks assigned to you make you wonder whether the engineers have ever heard of gravity. In the latest task, you must evaluate a model of a construction project.

The model is built by dropping axis-aligned squares toward the ground, which is the line $y=0$ . Each square has a fixed $x$ coordinate and size. A square moves downward until its bottom face touches the ground or another square. Once a square lands, it is fastened in place, so even if two squares are off balance, they do not fall over.

Given the squares and the order in which to drop them, find the maximum $y$ coordinate that the structure reaches after each square is placed.

Input

The first line contains an integer $N$ ( $1 \le N \le 10^5$ ), the number of squares. Each of the next $N$ lines describes a square in the order it is 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$ ), the $x$ coordinate of the left edge of square $i$ and its size.

Output

Print $N$ lines. Line $i$ contains the highest $y$ coordinate reached by the structure after squares $1,\dots,i$ have been dropped.

Examples4

Example 1
Input
```
3
0 1
0 2
0 3
```
Expected output
```
1
3
6
```
Example 2
Input
```
5
0 1
0 10
9 1
0 10
9 10
```
Expected output
```
1
11
12
22
32
```
Example 3
Input
```
3
0 1
1 1
2 1
```
Expected output
```
1
1
1
```

Example 4

Input

Expected output