有序表的最小和

Description

给出两个长度为n的有序表A和B，在A和B中各任取一个元素，可以得到n^2个和，求这些和中最小的n个

Input

第一行包含一个整数n（n≤400000n≤400000）

第二行与第三行分别有n个整数，分别代表有序表A和B，整数之间由一个空格隔开，大小在长整数范围之内，保证有序表的数据单调递增。

Output

输出共n行，每行一个整数，第i行为第i小的和，数据保证在长整数范围之内

Samples

Input

1
2
3

3
1 2 5
2 4 7

Output

1
2
3

3
4
5

AC CODE：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7; 
const int INF = 0x3f3f3f3f ;
const int N = 4e5 + 5;
int a[N],b[N];
struct node {
	int w;
	int i,j;
	friend bool operator< (node a,node b) {
		return a.w > b.w;
	}
};
priority_queue<node> q;
int main(){
	int n,x,y;
	cin>>n;
	for(int i=1;i<=n;i++)	
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) {
		scanf("%d",&b[i]);
		q.push({a[i]+b[1],i,1});
	}
	for(int i=1;i<=n;i++) {
		node tmp = q.top();q.pop();
		printf("%d\n",tmp.w);
		x = tmp.i,y = tmp.j;
		tmp.w = a[x]+b[y+1];
		tmp.j++; 
		q.push(tmp);
	}
 	return 0;
}