题目描述

在银河系的遥远角落，宇宙大帝 Luke 时常举办各种奇异的挑战赛，以此来激发年轻探险者们的潜能。这一次，他邀请了一位聪明过人的小女孩 SK 来到他的星球 Lu3KO5。Luke 准备了一场独特的智力挑战，所有的银河居民都在关注着这场比赛。

为了考验 SK 的智慧，Luke 召唤出了两个神秘的时空袋子，袋子 $A$ 和袋子 $B$。这两个袋子拥有吸引宇宙中不同数字的能力，能够将这些数字封存在袋子中。比赛共有 $n$ 轮，每一轮，Luke 都会从宇宙的时间长河中提取出两个神秘的数字 $a$ 和 $b$，分别放入袋子 $A$ 和袋子 $B$ 中。

然后，Luke 向 SK 提出挑战：如果她将袋子 $A$ 中的所有数字与袋子 $B$ 中的所有数字按照时空法则一一配对，她需要找出其中配对后和最大的那一对的最小值。只有得出正确答案，她才能继续接受下一轮的挑战。

SK 思维敏捷，很快就找到了答案。但是为了确保万无一失，她决定在回答 Luke 之前，先找你确认一下她的答案是否正确。现在，银河的命运掌握在你们手中，能否帮助 SK 通过这场挑战呢？

输入格式

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

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

输出格式

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

样例输入 #1

3
2 8
3 1
1 4

样例输出 #1

10
10
9

数据范围

【样例 1 解释】

对于第一组询问 $2+8=10$。

对于第二种询问 $2+8=10,3+1=4$。

对于第三组询问 $1+8=9,3+1=4,2+4=6$。

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

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

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