Sixth Sense

Ms. Future is gifted with precognition. Naturally, she is excellent at some card games since she can correctly foresee every player's actions, except her own. Today, she accepted a challenge from a reckless gambler Mr. Past. They agreed to play a simple two-player trick-taking card game.

Cards for the game have a number printed on one side, leaving the other side blank making indistinguishable from other cards.

A game starts with the same number, say $n$, of cards being handed out to both players, without revealing the printed number to the opponent.

A game consists of $n$ tricks. In each trick, both players pull one card out of her/his hand. The player pulling out the card with the larger number takes this trick. Because Ms. Future is extremely good at this game, they have agreed to give tricks to Mr. Past when both pull out cards with the same number. Once a card is used, it can never be used later in the same game. The game continues until all the cards in the hands are used up. The objective of the game is to take as many tricks as possible.

Your mission of this problem is to help Ms. Future by providing a computer program to determine the best playing order of the cards in her hand. Since she has the sixth sense, your program can utilize information that is not available to ordinary people before the game.

Input

The input consists of a single test case of the following format.


$n$
$p_1$ ... $p_n$
$f_1$ ... $f_n$


$n$ in the first line is the number of tricks, which is an integer between 2 and 5000, inclusive. The second line represents the Mr. Past's playing order of the cards in his hand. In the $i$-th trick, he will pull out a card with the number $p_i$ ($1 \leq i \leq n$). The third line represents the Ms. Future's hand. $f_i$ ($1 \leq i \leq n$) is the number that she will see on the $i$-th received card from the dealer. Every number in the second or third line is an integer between 1 and 10 000, inclusive. These lines may have duplicate numbers.

Output

The output should be a single line containing $n$ integers $a_1 ... a_n$ separated by a space, where $a_i$ ($1 \leq i \leq n$) is the number on the card she should play at the $i$-th trick for maximizing the number of taken tricks. If there are two or more such sequences of numbers, output the lexicographically greatest one among them.

Sample Input 1


5
1 2 3 4 5
1 2 3 4 5


Sample Output 1


2 3 4 5 1


Sample Input 2


5
3 4 5 6 7
1 3 5 7 9


Sample Output 2


9 5 7 3 1


Sample Input 3


5
3 2 2 1 1
1 1 2 2 3


Sample Output 3


1 3 1 2 2


Sample Input 4


5
3 4 10 4 9
2 7 3 6 9


Sample Output 4


9 7 3 6 2






Example

Input

5
1 2 3 4 5
1 2 3 4 5


Output

2 3 4 5 1
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 10005

int N;
int P[5005],F[5005];
vector<int> V;
int P_table[NUM],F_table[NUM];
int P_TMP[NUM],F_TMP[NUM];

int calc(){

	for(int i = 0; i < NUM; i++){

		P_TMP[i] = P_table[i];
		F_TMP[i] = F_table[i];
	}

	int P_num = 1,F_num = 2;
	int ret = 0;

	while(true){

		while(P_num < NUM && P_TMP[P_num] == 0)P_num++;
		while(F_num < NUM && (P_num >= F_num || F_TMP[F_num] == 0))F_num++;

		if(F_num == NUM)break;

		while(F_TMP[F_num] > 0 && P_TMP[P_num] > 0){
			F_TMP[F_num]--;
			P_TMP[P_num]--;
			ret++;
		}
	}

	return ret;
}

int main(){

	for(int i = 0; i < NUM; i++){

		P_table[i] = 0;
		F_table[i] = 0;
	}

	scanf("%d",&N);

	for(int i = 0; i < N; i++){

		scanf("%d",&P[i]);
		P_table[P[i]] += 1;
	}

	for(int i = 0; i < N; i++){

		scanf("%d",&F[i]);
		F_table[F[i]] += 1;
		V.push_back(F[i]);
	}

	int max_num = calc();

	sort(V.begin(),V.end());

	queue<int> ANS;
	int num_larger = 0;
	int left,right,mid,this_value,tmp_larger,index;

	for(int i = 0; i < N; i++){

		this_value = -1;
		left = 0,right = V.size()-1,mid = (left+right)/2;

		while(left <= right){

			F_table[V[mid]] -= 1;
			P_table[P[i]] -= 1;

			tmp_larger = calc();

			F_table[V[mid]] += 1;
			P_table[P[i]] += 1;

			if(V[mid] <= P[i]){

				if(num_larger+tmp_larger == max_num){

					this_value = V[mid];
					index = mid;

					left = mid+1;
				}else{

					if(V[V.size()-1] <= P[i]){

						right = mid-1;

					}else{

						left = mid+1;
					}
				}

			}else{

				if(num_larger+tmp_larger+1 == max_num){

					this_value = V[mid];
					index = mid;
					left = mid+1;

				}else{

					right = mid-1;
				}
			}
			mid = (left+right)/2;
		}

		ANS.push(this_value);

		if(this_value > P[i]){

			num_larger++;
		}
		F_table[this_value] -= 1;
		P_table[P[i]] -= 1;
		V.erase(V.begin()+index);
	}

	printf("%d",ANS.front());
	ANS.pop();

	while(!ANS.empty()){

		printf(" %d",ANS.front());
		ANS.pop();
	}
	printf("\n");

	return 0;
}

