Sherlock Bourne is the best spy of CIA. He has two lists. Each of them has N integers, and he often encrypts his message by this rule: each time he picks one number from one list and pluses another number from the other list to get a new number. After N^2 times, he will get N^2 numbers. And then he will pick the smallest N numbers to be the codes of his message. Now, can you help him do this job?

输入格式

There are multiple test cases in the input file. Each test case contains three lines. The first line contains one integer N(1 <= N <= 50000). Two lines follow, each contains N numbers of one number list. Each number is less than 2^15.

输出格式

You should output one line, contains the N numbers which will be used as the codes of the message by increasing order. There is a blank between each number.

样例输入

3
1 2 3
1 2 3

样例输出

2 3 3

通过的代码：

#include <iostream>
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
int n,num1[50000],num2[50000];
int main() {
	int i,j,k,l;
	priority_queue<int,deque<int>,less<int> > big;
	while(scanf("%d",&n)!=EOF) {
		for(i=0; i<n; i++)
			scanf("%d",&num1[i]);
		sort(num1,num1+n);
		for(j=0; j<n; j++) {
			scanf("%d",&num2[j]);
			big.push(num1[0]+num2[j]);
		}
		sort(num2,num2+n);
		for(k=1; k<n; k++)
			for(l=0; l<n; l++) {
				if(num1[k]+num2[l]>big.top())
					break;
				big.pop();
				big.push(num1[k]+num2[l]);
			}
		for(k=0; k<n; k++) {
			num1[n-k-1]=big.top();
			big.pop();
		}
		printf("%d",num1[0]);
		for(i=1; i<n; i++)
			printf(" %d",num1[i]);
	}
	return 0;
}

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int a[50000],b[50000],c[50000];
void insertc(int tmp,int n) {
	int i=n-1;
	while(c[i] > tmp) {
		c[i] = c[i-1];
		i--;
	}
	c[i+1] = tmp;
}
int main() {
	int n,i,j,tmp;
	while(scanf("%d",&n)!=EOF) {
		for (i=0; i<n; i++) scanf("%d",&a[i]);
		sort(a,a+n);
		for (i=0; i<n; i++)
			scanf("%d",&b[i]);
		sort(b,b+n);
		for (i=0; i<n; i++)
			c[i]=a[0]+b[i];
		for (i=1; i<n; i++)
			for (j=0; j<n; j++) {
				tmp = a[i] + b[j] ;
				if (tmp < c[n-1]) insertc(tmp,n);
				else break;
			}
		printf("%d",c[0]);
		for(int i=1; i<n; i++)
			printf(" %d",c[i]);
	}
	return 0;
}