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 \times 10^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$)。

样例

样例输入 1

5
2 2
3 2
4 4
5 6
6 6

样例输出 1

0
0
0
0

样例输入 2

3
4 100
5 98
1 100

样例输出 2

-95
-96