4375: B. 鲁的女孩 (girl.c/cpp/pas)
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
在银河系的遥远角落，宇宙大帝 Luke 时常举办各种奇异的挑战赛，以此来激发年轻探险者们的潜能。这一次，他邀请了一位聪明过人的小女孩 SK 来到他的星球 Lu3KO5。Luke 准备了一场独特的智力挑战，所有的银河居民都在关注着这场比赛。
为了考验 SK 的智慧，Luke 召唤出了两个神秘的时空袋子，袋子 $A$ 和袋子 $B$。这两个袋子拥有吸引宇宙中不同数字的能力，能够将这些数字封存在袋子中。比赛共有 $n$ 轮，每一轮，Luke 都会从宇宙的时间长河中提取出两个神秘的数字 $a$ 和 $b$，分别放入袋子 $A$ 和袋子 $B$ 中。
然后，Luke 向 SK 提出挑战：如果她将袋子 $A$ 中的所有数字与袋子 $B$ 中的所有数字按照时空法则一一配对，她需要找出其中配对后和最大的那一对的最小值。只有得出正确答案，她才能继续接受下一轮的挑战。
SK 思维敏捷，很快就找到了答案。但是为了确保万无一失，她决定在回答 Luke 之前，先找你确认一下她的答案是否正确。现在，银河的命运掌握在你们手中，能否帮助 SK 通过这场挑战呢？
输入
### Input
输入第一行为一个整数 $n$，表示比赛的轮数。
接下来 $n$ 行，每行包含两个整数 $a$ 和 $b$，分别表示每轮中放入袋子 $A$ 和袋子 $B$ 的神秘数字。
输出
### Output
输出 $n$ 个整数，第 $i$ 个整数表示将前 $i$ 个袋子 $A$ 和前 $i$ 个袋子 $B$ 中所有数字一一配对后，和最大的一对的最小值。
样例输入 复制
3
2 8
3 1
1 4样例输出 复制
10
10
9提示
### Examples
#### 【样例 1 输入】
```input
3
2 8
3 1
1 4
```
#### 【样例 1 输出】
```output
10
10
9
```
#### 【样例 1 解释】
对于第一组询问 $2+8=10$。
对于第二种询问 $2+8=10,3+1=4$。
对于第三组询问 $1+8=9,3+1=4,2+4=6$。
#### 【样例 2,3 输入】
见下发文件。
#### 【样例 2,3 输出】
见下发文件。
### Notes
对于 $30\%$ 的数据，$n \le 20$。
对于 $50\%$ 的数据，$n \le 100$。
对于 $100\%$ 的数据，$n \le 10^5, 1 \le a, b \le 100$。