题目描述

徐老师有两本小本子，一开始两个小本子都是空白的

接着徐老师将会在两本小本子上分别依次写下 $n$ 个数字

写数字的方式如下：

1. 同时翻开两个小本子的第一页，并分别写下一个数字
2. 同时将两个小本子向后翻一页，并分别写下一个数字
3. 重复 $n-1$ 次 $2$ 操作

现在徐老师决定用这两本小本子来考验考验你的智商

我们将两个小本子称为 $A$ 和 $B$，第 $i$ 页上的数字为 $A_i$ 和 $B_i$

每当徐老师写下一组数字，徐老师就会发出提问：现在你可以按照任意顺序重新排列 $A$ 中的数字或者 $B$ 中的数字，在重排（也可以不排）后得到 $C_i = A_i+B_i$，请问如何重排可以使得 $max(C_i)$ 最小？这个最小值是多少？

输入格式

输入第一行是一个整数 $n$，表示徐老师将会写下的数字 接下来 $n$ 行，每行包含两个整数 $A_i$ 和 $B_i$ 分别表示徐老师这一次在两个小本子里分别写下的数字

输出格式

输出包含 $n$ 行，徐老师每次写下一个数字后的答案

数据范围

对于 $20\%$ 的数据，$1\leq n\leq 5,1\leq A_i,B_i\leq 10$；

对于 $40\%$ 的数据，$1\leq n\leq 100,1\leq A_i,B_i\leq 100$；

对于 $70\%$ 的数据，$1\leq n\leq 10^3,1\leq A_i,B_i\leq 100$；

对于 $100\%$ 的数据，$1\leq n\leq 10^5,1\leq A_i,B_i\leq 100$。

样例输入

3
2 8
3 1
1 4

样例输出

10
10
9

样例解释

第一次输入数字，$A$ 上数字为 $[2]$, $B$ 上数字为 $8$，得到 $max(C_i) = 2+8=10$ 第二次输入数字，将 $A$ 重排为 $[2,3]$, $B$ 重排为 $[8,1]$ 得到 $max(C_i)=2+8=10$ 第三次输入数字，将 $A$ 重排为 $[1,2,3]$, $B$ 重排为 $[8,1,4]$，得到 $max(C_i)=1+8=9$ 可以发现没有其他重排方案可以使得 $max(C_i)$ 更小