Minimizing the Maximum Pair Sum

Mirko and Slavko are playing a game consisting of $N$ rounds. In the $k$-th round, Slavko gives two integers $A_k$ and $B_k$. For the first $k$ rounds, you are given the sequences $A = [A_1, A_2, \ldots, A_k]$ and $B = [B_1, B_2, \ldots, B_k]$. Your task is to pair these numbers into $k$ pairs $(A_i, B_j)$ (with $1 \le i,j \le k$) in such a way that every number from both sequences is used exactly once, and the maximum pair sum, i.e. $\max\{A_i+B_j\}$, is minimized.

It can be shown that pairing the smallest number from $A$ with the largest number from $B$, the second smallest with the second largest, and so on, results in the optimal solution.

inputFormat

The input begins with a single integer $N$ representing the number of rounds. Each of the next $N$ lines contains two space-separated integers $A_k$ and $B_k$ for the $k$-th round.

Example:

3
1 3
4 2
2 1

outputFormat

Output $N$ lines. The $k$-th line should contain the minimum possible maximum pair sum achievable by optimally pairing the sequences of $A$ and $B$ from the first $k$ rounds.

Example Output:

4
6
5

sample

1
5 10

15