Mirko 饿得像只熊——不对，是像个程序员——他偶然来到了一家当地的餐馆。这家餐馆提供 $N$ 种菜品，并且有一个有趣的定价策略：每种菜品 $i$ 有两个指定的价格 $A_i$ 和 $B_i$。Mirko 仅对第一道点下的菜品支付其对应的 $A$ 价格，而对于所有其他点下的菜品，则支付其对应的 $B$ 价格。

Mirko 无法决定要点多少道菜。为了让他更容易做出决定，他请你计算：对于每个介于 $1$ 到 $N$ 之间（含）的 $k$，点恰好 $k$ 道不同的菜所需的最小总价格。Mirko 不关心他具体点了哪些菜，也不关心点菜的顺序，但他不会重复点同一种菜。

输入格式

输入的第一行包含一个正整数 $N$ ($2 \le N \le 500\,000$)，表示餐馆提供的不同菜品数量。

接下来的 $N$ 行，每行包含两个正整数 $A_i$ 和 $B_i$ ($1 \le A_i, B_i \le 1\,000\,000\,000$)，表示上述菜品 $i$ 的价格。

输出格式

输出必须包含 $N$ 行，其中第 $k$ 行包含点恰好 $k$ 道不同菜品的最小价格。

样例

输入样例 1

3
10 5
9 3
10 5

输出样例 1

9
13
18

输入样例 2

2
100 1
1 100

输出样例 2

1
2

输入样例 3

5
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

输出样例 3

1000000000
2000000000
3000000000
4000000000
5000000000

说明

第一个样例的解释：

• $k = 1$：Mirko 支付 $A_2 = 9$ 作为起手菜品 2 的价格。
• $k = 2$：Mirko 支付 $A_1 = 10$ 作为起手菜品 1 的价格，然后支付 $B_2 = 3$ 作为菜品 2 的价格。
• $k = 3$：Mirko 支付 $A_1 = 10$ 作为起手菜品 1 的价格，然后支付 $B_2 = 3$ 作为菜品 2 的价格，最后支付 $B_3 = 5$ 作为菜品 3 的价格。