402508: GYM100796 B Wet Boxes

Memory Limit:256 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Wet Boxestime limit per test0.7 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Bob works in a warehouse which contains a large pile of boxes. The position of a box can be described with a pair of integers (x, y). Each box either stands on the ground (y = 0) or stands on top of two boxes with positions (x, y - 1) and (x + 1, y - 1) (see the figure).

Sometimes the contents of a box leak out and the box gets wet. When a box becomes wet, so do the two boxes below it. Given a list of boxes that leak in succession, help Bob count how many dry boxes became wet after each leak. Don't include boxes that were already wet.

Input

The first line contains a single integer n, the number of leaking boxes (1 ≤ n ≤ 105). The i-th of the next n lines contains two space-separated integers xi and yi, the position of the i-th leaking box (0 ≤ xi, yi ≤ 109).

Output

Output n lines: in the i-th line output the number of boxes that became wet after the i-th box had leaked.

ExamplesInput
4
1 3
3 2
0 6
1 1
Output
10
3
15
0

加入题单

上一题 下一题 算法标签: