题目描述

$kkkw$又来玩数字游戏了。这次的规则是这样的:

最开始有两个空的数列$A$和 $B$，第$i$次$kkkw$会给数列 $A$ 和$B$分别加一个数 $A_i, B_i$,然后你可以将 $A$ 和 $B$ 以任意方式重新排序，使得所有$A_i+ B_i$的最大值最小。

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

输入格式

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

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

输出格式

输出包括 $N$ 行，对于每一次$kkkw$ 给出的数字，求出所求排列中对应 $A_i+B_i$最大值的最小值

3
2 8
3 1
1 4

10
10
9

3
1 1
2 2
3 3

2
3
4

说明/提示

样例1

读入 2,8，最大值的最小值为 2+8=10。

读入 3,1，最大值的最小值为2+8=10。

读入 1,4，最大值的最小值为1+8=9。

$30 \%$的数据，$1 \le N \le 200$

$50 \%$的数据，$1 \le N \le 1000$

$100 \%$的数据，$1 \le N \le 10^5,1 \le A_i,B_i \le 100$