题目描述

Ho 为了她的秘密出差，抵达了一个秘密地点。她知道这次出差最多持续 $N$ 天，也可能更短，但她不确定具体的天数。因此，追求完美的 Ho 想要为所有可能的出差时长，即从 $1$ 天到 $N$ 天，制定每日的用餐清单。

在这个秘密地点，恰好只有一个美食广场（碰巧）提供 $2N$ 种不同的菜单。美食广场只在午餐时间和晚餐时间营业，而且奇怪的是，同一菜单的午餐和晚餐价格可能不同。

她将在整个出差期间，每天午餐和晚餐各吃一种菜单，并且在整个行程中从不重复吃同一种菜单。她完全不关心吃的是哪种菜单，唯一重要的是总餐费必须最小化。

在这些条件下，她本可以制定她的用餐清单，但意识到写下总共 $N(N+1)$ 个菜单是困难且累人的。因此，她没有制定用餐清单，而是计算了当 $i$ 从 $1$ 到 $N$ 时，$i$ 份午餐菜单和 $i$ 份晚餐菜单的最小总价格。

作为 Ho 的忠实粉丝，你有一个至高无上的任务：输出她计算出的这 $N$ 个价格。

输入格式

第一行包含一个整数 $N$。 ($1 \leq N \leq 250 000$)

接下来的 $2N$ 行，每行包含两个整数 $l, d$，分别表示该菜单作为午餐和晚餐时的价格。 ($1 \leq l, d \leq 10^9$)

输出格式

输出 $N$ 行。第 $i$ 行应包含一个整数，表示 $i$ 份午餐菜单和 $i$ 份晚餐菜单的最小总价格。

1
4 9
5 3

7

2
1 6
2 4
5 3
3 1

2
7

4
7 5
5 7
7 4
4 2
2 5
6 4
3 2
1 9

3
7
16
26

提示

翻译由 DeepSeek 完成