Amy and Bob are good friends. Today they want to play a game.

Here is the process about it:

1. There are $n$ items in total. The $i^{th}$ item has $a_i$ points to Amy and $b_i$ points to Bob.
2. Bob takes $m$ items out of the game, so neither of them can pick these items. ($0\le m\le n-2$)
3. Amy picks one item first, assume she takes $j^{th}$ item, then she gets $a_j$ points.
4. Bob picks one item, assume he takes $k^{th}$item, then he gets $b_k$ points.$k\neq j$
5. The game ends.

Now they are wondering what is the value of $a_j-b_k$ if they play optimally.

(Amy wants $a_j-b_k$ to be maximum, Bob wants $a_j-b_k$ to be minimum)

Please help them calculate the value when $m$ is in $[0, n-2]$.

Input

The first line contains one integer,

$n$ ($1 \le n \le 3\times10^5$) ---

the number of items.

Each of the next $n$ lines contains two integers,

$a_i$ and $b_i$($1\le a_i, b_i\le 10^9$)---

meaning the $i^{th}$item has $a_i$ value to Amy and $b_i$ value to Bob.

Output

Output $n - 1$integers, each of them in one line.

The $i^{th}$line is the value of $a_j - b_k$ when Bob bans exactly $i-1$ items

($1\le i\le n-1$)

Sample Input 1

5
2 2
3 2
4 4
5 6
6 6

Sample Output 1

0
0
0
0

Sample Input 2

3
4 100
5 98
1 100

Sample Output 2

-95
-96