在银河系的遥远角落，宇宙大帝 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 中所有数字一一配对后，和最大的一对的最小值。

数据范围

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

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

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

【样例 1 解释】

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

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

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

CSP-J模拟赛