Problem Statement

You are given two integer sequences A and B of length N. For $k = 1, 2, \ldots, N,$ solve the following problem:

• Consider choosing k distinct integers between 1 and N, inclusive. Let S be the set of chosen integers. Find the maximum value of $\displaystyle (\sum_{i \in$ $S} A_i) - \max_{i \in$ S} B_i.

Input

The input is given from Standard Input in the following format:
N
A_1 B_1
A_2 B_2
$\vdots$
A_N B_N

Output

Print N lines. The i-th line should contain the answer to the problem for k=i.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• -$10^9 \leq A_i \leq 10^9$
• -$2 \times 10^{14} \leq B_i \leq 2 \times 10^{14}$

Sample Input 1

3
4 1
5 6
3 2

Sample Output 1

3
5
6

The following choices are optimal.

• k = 1: S = {1}
• k = 2: S = {1, 3}
• k = 3: S = {1, 2, 3}

Sample Input 2

2
0 1
0 1

Sample Output 2

-1
-1

Sample Input 3

6
9 7
2 4
7 1
-1000 0
3 4
8 5

Sample Output 3

6
10
17
20
22
-978

见题面 Input 部分

见题面 Output 部分