Description

小闪最近迷上了二刀流——不过他耍的其实是剑——新买了一个宝库用来专门存放自己收集的双剑。一对剑有两把，分只能左手用的和只能右手用的，各自有一个攻击力数值。虽然一对剑在小闪刚拿到时是一对，不过其实可以认为它们是独立的两把剑。一对剑的攻击力是左右两把剑的攻击力之和，小闪可以自由地搭配左右剑来练习二刀流。每次小闪得到一对新的双剑，他都可以去更新一次自己的双剑宝库，重新给每把剑配对。小闪需要自己给每一把剑配对，然后他的智能宝库会提供宝库中攻击力最高的一对剑来给小闪练习；不过小闪其实是一个很低调的人，不喜欢锋芒毕露，希望自己练习时的双剑攻击力尽可能小——虽然不知道怎么改变宝库，但是他可以改变双剑的搭配。每次新得到一对剑，更新完宝库之后，小闪练习时用的剑可能就会发生变化。请你求出每次更新宝库后小闪练习二刀流时的双剑攻击力。

Input

输入包含不超过10组数据。对于每组数据，第一行一个整数N(1<=N<=100000)，表示小闪前后共收集到了N对双剑；接下来N行，每行包含两个整数A和B（1<=A,B<=100），分别表示每次小闪收集到的一对剑的左手用剑和右手用剑的攻击力数值。每组数据之后会有一个空行。输入以一行一个整数0结束。

Output

对于每组数据，输出N行，每行一个整数，表示每次更新后小闪练习二刀流时的双剑攻击力值。相邻两组数据之间输出一个空行。

Sample Input

3
2 8
3 1
1 4

3
1 1
2 2
3 3

0

Sample Output

10
10
9

2
3
4
 
 
  
Hint
 
 
  开始看到这题，sort一下把最大和最小加起来判断一下，结果TLE 
   
  然后在输入的时候判断最大最小，TLE 
 
  仔细想了想就算不TLE还是会wa 
   
  然后看到剑的能量最大就100，就想到用数组记录各能量的剑的个数，输入时不断更新就可以了 
 
  
 
 
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int l[105], r[105];
int main()
{
	int T,a,b;
	while (~scanf("%d", &T))
	{
		if (!T)
			break;
		memset(l, 0, sizeof(l));
		memset(r, 0, sizeof(r));
		int maxx=100,minn=0;
		for (int i = 1; i <= T; i++)
		{
			scanf("%d%d", &a, &b);
			l[a]++, r[b]++;
			if (maxx>a)maxx = a;
			if (minn < b)minn = b;
			int m = maxx, n = minn,ma=0;
			int p = l[maxx], q = r[minn];
			int cnt = 0;
			while (cnt != i)
			{
				if (p == 0)
				{
					p = l[++m];
					continue;
				}
				if (q == 0)
				{
					q = r[--n];
					continue;
				}
				if (m + n > ma)ma = m + n;
				if (p == q)
				{
					cnt += p; m++; n--;
					p = l[m]; q = r[n];
				}
				else if (p < q)
				{
					q -= p;
					cnt += p;
					p = l[++m];
				}
				else if (p>q)
				{
					p -= q;
					cnt += q;
					q = r[--n];
				}
			}
			printf("%d\n", ma);
		}
		printf("\n");
	}
}
/**********************************************************************
	Problem: 1900
	User: leo6033
	Language: C++
	Result: AC
	Time:444 ms
	Memory:2024 kb
**********************************************************************/