Number Game

Time limit1sMemory limit128 MB

Summary

After each new pair of numbers arrives, pair sorted A values with reverse sorted B values and output the minimum possible maximum sum, updating online for each round.

Level: Medium5 of 10
Topics: Greedy, Sorting, Implementation
Solved: No attempts yet

Problem

Changyoung and Hyunwoo are playing a number game made of several rounds. At the start of each round, Hyunwoo gives Changyoung two positive integers A and B, each less than 100.

Using every A value seen so far and every B value seen so far exactly once, Changyoung must form pairs. The goal is to make the largest value of A+B among all pairs as small as possible.

If the current round is the N-th round, the numbers seen so far are a1, a2, ..., aN and b1, b2, ..., bN. Form N pairs using every ai and every bj exactly once, and find the minimum possible value of the maximum pair sum.

Input

The first line contains the number of rounds N. (1 ≤ N ≤ 100000)

Each of the next N lines contains the two numbers A and B announced in that round. (1 ≤ A, B < 100)

Output

After each round, print one line containing the minimum possible maximum pair sum using all numbers seen so far.

Examples2

Example 1
Input
```
3
2 8
3 1
1 4
```
Expected output
```
10
10
9
```
Example 2
Input
```
3
1 1
2 2
3 3
```
Expected output
```
2
3
4
```