CCMALI - MALI

Mirko and Slavko are playing a new game. Again. Slavko starts each round by giving Mirko two numbers A and B, both smaller than 100. Mirko then has to slove the following task for Slavko: how to pair all given A numbers with all given B numbes so that the maximal sum of such pairs is as small as possible.

In other words, if during previous rounds Slavko gave numbers a1, a2, a3 .... an and b1, b2, b3 ... bn, determine n pairings (ai, bj) such that each number in A sequence is used in exactley one pairing, and each number in B sequenct is used in exactely one pairing and the maximum of all sums ai + bj is minimal.

Input

The first line of input contains a single integer N (1 ≤ N ≤ 100000), number of rounds. Next N lines contain two integers A and B (1 ≤ A, B ≤ 100), numbers given by Slavko in that round.

Output

Output consists of N lines, one for each round. Each line should contain the smallest maximal sum for that round.

Example

Input1:
3
2 8
3 1
1 4 Output1: 10
10
Input2:
3
1 1
2 2
3 3 
Output2:
2
3
4 

Added by:Hacker7
Date:2014-05-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CROATIAN OPEN COMPETITION IN INFORMATICS 2009/2010 CONTEST 1

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.