You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Z 和小 Y 又在玩数字游戏了。

这次的规则是这样的：最开始有两个空的数列 $A$ 和 $B$，第 $i$ 次小 Y 会在数列 $A$ 和 $B$ 的末尾分别添加一个数 $A_i，B_i$，而小 Z 可以将 $A$ 和 $B$ 以任意方式重新排序，使得所有 $A_i+B_i$ 的最大值最小。

请你帮小 Z 在每一次小 Y 给出两个新的数之后，求出 $A_i+B_i$ 最大值的最小值。

输入格式

从 mali.in 文件输入数据。

第一行包括一个正整数 $N$，表示小 Y 给出数字的次数。

接下来 $N$ 行，第 $i+1$ 行包括 $2$ 个正整数 $A_i，B_i$，表示每一次小 Y 给出的数对。

输出格式

输出到 mali.out 文件。

输出包括 $N$ 行，对于每一次小 Y 给出的数字，求出所求排列中对应 $A$ 和 $B$ 之和的最大值的最小值。

样例

3
2 8
3 1
1 4

10
10
9

3
1 1
2 2
3 3

2
3
4

说明/提示

样例 1 解释

第一组样例解释：

• 第一次询问后：$A=\{2\}, B=\{8\}, \min\{A_i+B_i\}=2+8=10$;
• 第二次询问后，小 Z 可以将序列排列为 $A = \{2,3\}, B=\{8,1\}$，其中 $A_1+B_1=10,A_2+B_2=4$，最大值为 $10$，并且通过枚举可以证明，这种方式排列的两个序列，他们的和的最大值最小。
• 第三次询问后， 小 Z 可以将序列排列为 $A=\{1, 2, 3\}, B=\{8, 1, 4\}$，其中 $A_1+B_1=9, A_2+B_2=3, A_3+B_3=7$，最大值为 $9$，并且通过枚举可以证明，这种方式排列的两个序列，他们的和的最大值最小。

数据范围

对于 $50\%$ 的数据，有 $N≤200$；

对于 $100\%$ 的数据，有 $1≤N≤100000,1≤A_i,B_i≤100$。