题面翻译

给出 $N$，以及 $A_{1...N},B_{1...N}$。

对于每个 $k\in [1,N]$，找出一个 $1...N$ 的集合 $S$，满足 $|S|=k$ 且 $\sum\limits_{i\in S}A_i-\max\limits_{i\in S}B_i$ 最大，输出这个值。

$1\le N\le 2\times 10^5,\space |A_i|\le 10^9,\space |B_i|\le 2\times 10^{14}$

输入格式

第一行给出数字N

接下来N行2列，第一列描述a数组，第二列描述数组

输出格式

如题

样例 #1

样例输入 #1

3
4 1
5 6
3 2

样例输出 #1

3
5
6

样例 #2

样例输入 #2

2
0 1
0 1

样例输出 #2

-1
-1

样例 #3

样例输入 #3

6
9 7
2 4
7 1
-1000 0
3 4
8 5

样例输出 #3

6
10
17
20
22
-978

提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $-10^9\ \leq\ A_i\ \leq\ 10^9$
• $ -2\ \times\ 10^{14}\ \leq\ B_i\ \leq\ 2\ \times\ 10^{14} $

Sample Explanation 1

以下の選び方がそれぞれ最適です。 - $k\ =\ 1$ : $S\ =\ \{1\}$ - $k\ =\ 2$ : $S\ =\ \{1,\ 3\}$ - $k\ =\ 3$ : $S\ =\ \{1,\ 2,\ 3\}$