P17739 [ICPC 2019 Xuzhou R] Interesting game

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

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