33OJ
登录 注册

#P17739. [ICPC 2019 Xuzhou R] Interesting game

[ICPC 2019 Xuzhou R] Interesting game

Problem Description

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

Here is the process about it:

  1. There are nn items in total. The ithi^{th} item has aia_i points to Amy and bib_i points to Bob.
  2. Bob takes mm items out of the game, so neither of them can pick these items. (0≤m≤n−20\le m\le n-2)
  3. Amy picks one item first, assume she takes jthj^{th} item, then she gets aja_j points.
  4. Bob picks one item, assume he takes kthk^{th} item, then he gets bkb_k points. k≠jk\neq j
  5. The game ends.

Now they are wondering what is the value of aj−bka_j-b_k if they play optimally.

(Amy wants aj−bka_j-b_k to be maximum, Bob wants aj−bka_j-b_k to be minimum)

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

Input Format

The first line contains one integer, nn (1≤n≤3×1051 \le n \le 3\times10^5) --- the number of items.

Each of the next nn lines contains two integers, aia_i and bib_i(1≤ai,bi≤1091\le a_i, b_i\le 10^9)--- meaning the ithi^{th}item has aia_i value to Amy and bib_i value to Bob.

Output Format

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

The ithi^{th} line is the value of aj−bka_j - b_k when Bob bans exactly i−1i-1 items (1≤i≤n−11\le i\le n-1)

5
2 2
3 2
4 4
5 6
6 6
0
0
0
0
3
4 100
5 98
1 100
-95
-96