该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

数字配对（number）

强哥是一位热爱数学挑战的学生，他经常参加学校组织的智力竞赛。最近，学校举办了一场独特的数字配对挑战赛，所有的同学都在关注着这场比赛。

为了考验强哥的数学能力，老师准备了两组数字卡片，分别放在盒子 $A$ 和盒子 $B$ 中。比赛共有 $n$ 轮，每一轮，老师都会从数字库中取出两个数字 $a$ 和 $b$，分别放入盒子 $A$ 和盒子 $B$ 中。

然后，老师向强哥提出挑战：如果他将盒子 $A$ 中的所有数字与盒子 $B$ 中的所有数字进行一一配对，他需要找出所有配对组合中，和最大的那一对数字的最小可能值。只有得出正确答案，他才能继续接受下一轮的挑战。

强哥思维敏捷，很快就找到了答案。但是为了确保万无一失，他决定在回答老师之前，先找你确认一下答案是否正确。现在，比赛的结果掌握在你们手中，能否帮助强哥通过这场挑战呢？

输入格式 (number.in)

输入第一行为一个整数 $n$，表示比赛的轮数。

接下来 $n$ 行，每行包含两个整数 $a$ 和 $b$，分别表示每轮中放入盒子 $A$ 和盒子 $B$ 的数字。

输出格式 (number.out)

输出 $n$ 个整数，第 $i$ 个整数表示将前 $i$ 轮盒子 $A$ 和盒子 $B$ 中所有数字一一配对后，和最大的那一对数字的最小可能值。

3
2 8
3 1
1 4

10
10
9

样例解释

• 第一轮：只有一对数字 $2+8=10$
• 第二轮：可能的配对有 $2+8=10$，$3+1=4$，最大和为 $10$
• 第三轮：最优配对为 $1+8=9$，$3+1=4$，$2+4=6$，最大和为 $9$

数据范围

对于 $30\%$ 的数据，$n \le 20$。

对于 $50\%$ 的数据，$n \le 100$。

对于 $100\%$ 的数据，$n \le 10^5$，$1 \le a, b \le 100$。