P17739 [ICPC 2019 Xuzhou R] Interesting game

Amy 和 Bob 是好朋友。今天他们想玩一个游戏。 游戏过程如下： 1. 总共有 $n$ 个物品。第 $i$ 个物品对 Amy 来说价值为 $a_i$，对 Bob 来说价值为 $b_i$。 2. Bob 先从游戏中移除 $m$ 个物品，这样两人都不能选择这些物品。（$0\le m\le n-2$） 3. Amy 首先选择一个物品，假设她拿了第 $j$ 个物品，则她得到 $a_j$ 分。 4. Bob 再选择一个物品，假设他拿了第 $k$ 个物品，则他得到 $b_k$ 分。$k\neq j$ 5. 游戏结束。 现在他们想知道，如果双方都采取最优策略，$a_j-b_k$ 的值是多少。 （Amy 希望 $a_j-b_k$ 尽可能大，Bob 希望 $a_j-b_k$ 尽可能小） 请你对于 $m$ 从 $0$ 到 $n-2$ 的每个取值，帮助他们计算出相应的值。

第一行包含一个整数 $n$（$1 \le n \le 3\times10^5$）—— 物品的数量。 接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1\le a_i, b_i\le 10^9$）—— 表示第 $i$ 个物品对 Amy 的价值为 $a_i$，对 Bob 的价值为 $b_i$。

输出 $n - 1$ 个整数，每行一个。 第 $i$ 行表示当 Bob 恰好移除 $i-1$ 个物品时，$a_j - b_k$ 的值。（$1\le i\le n-1$）

翻译由 DeepSeek V4 Pro 完成