Description

Mirko and Slavko are playing a game. The game has a total of $N$ rounds. In round $k$, Slavko gives two integers $A_k$ and $B_k$. Please help Mirko solve the following problem:

In the first $k$ rounds, Slavko has given the numbers $A_1, A_2, ..., A_k$ and $B_1, B_2, ..., B_k$. Pair these numbers into $k$ pairs $(A_i, B_j)$ ($1 \le i, j \le k$), such that every number in sequence $A$ and every number in sequence $B$ appears exactly once among these pairs, and the maximum value among the sums of all pairs ($A_i + B_j$) is minimized.

Input Format

The first line contains an integer $N$, indicating the number of rounds in the game.

The next $N$ lines each contain two integers $A_i, B_i$, indicating the two numbers Slavko gives in round $i$.

Output Format

Output $N$ lines. The $i$-th line should be the minimum possible maximum pair sum after round $i$.

3
2 8
3 1
1 4

10
10
9

3
1 1
2 2
3 3

2
3
4

Hint

Constraints

For $50\%$ of the testdata, $1 \le N \le 200$.

For $100\%$ of the testdata, $1 \le N \le 10^5$, $1 \le A_i, B_i \le 100$.

Notes

The scoring of this problem follows the original COCI problem settings, with a full score of $100$.

Translated from COCI2009-2010 CONTEST #1 T4 MALI.

Translated by ChatGPT 5