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$.

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}$

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$.