题目描述

噜噜有两条队列：左队列和右队列。一开始它们都是空的。
接下来会连续进行 $n$ 轮操作，每一轮噜噜都会把一个数字扔进左队列，同时把另一个数字扔进右队列。我们用

表示这 $n$ 组投入的数字（第 $i$ 行的 $a_i$ 进左队列，$b_i$ 进右队列）。

$\color{red}\text{游戏规则}$

• 在任意时刻，噜噜都可以随意重新排列左队列里的数字，也可以独立重新排列右队列里的数字（爱怎么排就怎么排，也可以不排）。

• 重新排列完成后，噜噜把两个队列“对齐配对”：第 $1$ 个左数配第 $1$个右数，第 $2$ 个配第 $2$ 个，依此类推。

• 对于每一对配对，计算它们的配对和 = 左数 + 右数。

• 噜噜关注的是所有配对和里最大的那个。排得越巧，这个最大值就可能越小。

任务：在第 $i$ 轮数字投入完毕后，立即告诉噜噜——
在此刻可随意重新排列两个队列的前提下，能把“最大的配对和”压到多小？
连续输出这 $n$ 个答案。

输入格式

第一行一个整数$n$,表示总共有$n$轮

接下来$n$行，每行$2$个整数,第$i$行表示 $a_i,b_i$ 分别代表第$i$轮加入左队列 和 右队列中的数字

输出格式

共 $n$ 行。
第 $i$ 行输出在前 $i$轮结束时，最小可能的“最大配对和”。

3
2 8
3 1
1 4

10
10
9

说明

• 只投第 $1$ 轮：左 $[2]$，右 $[8] \rightarrow$ 唯一配对和 $2+8=10$。

• 投完第 $2$ 轮：左 $[2,3]$ 排成 $[2,3]$，右 $[8,1]$ 排成 $[8,1]$，两对配对和分别为 $10、4$，最大值仍为 $10$（无法更小）。

• 投完第 $3$ 轮：把左排成 $[1,2,3]$，右排成 $[8,1,4]$，配对和为 $9、3、7$，最大值变成 $9$，为最优。

数据范围