Codeforces Round #429 (Div. 2)：C、&840A、 Leha and Function

题目：

Leha like all kinds of strange things. Recently he liked the function F(n, k). Consider all possible k-element subsets of the set [1, 2, ..., n]. For subset find minimal element in it. F(n, k) — mathematical expectation of the minimal element among all k-element subsets.

But only function does not interest him. He wants to do interesting things with it. Mom brought him two arrays A and B, each consists of m integers. For all i, j such that 1 ≤ i, j ≤ m the condition A_i ≥ B_j holds. Help Leha rearrange the numbers in the array A so that the sum is maximally possible, where A' is already rearranged array.

Input

First line of input data contains single integer m (1 ≤ m ≤ 2·10⁵) — length of arrays A and B.

Next line contains m integers a₁, a₂, ..., a_m (1 ≤ a_i ≤ 10⁹) — array A.

Next line contains m integers b₁, b₂, ..., b_m (1 ≤ b_i ≤ 10⁹) — array B.

Output

Output m integers a'₁, a'₂, ..., a'_m — array A' which is permutation of the array A.

Examples

Input

5
7 3 5 3 4
2 1 3 2 3

Output

4 7 3 5 3

Input

7
4 6 5 8 8 2 6
2 1 2 2 1 1 2

Output

2 6 4 5 8 8 6

题意：给出a、b两个数组，a数组任意一个数都大于b数组的任意一个数，将a数组重新排列使得 最大

思路：题目有给出提示：定义F(n,k)：F(n, k)是在集合{1, 2, 3, ..., n}中所有的具有k个元素的子集中分别取最小值，相加后的期望。For example, let's find F(4, 2). All possible 2-element subsets of {1,2,3,4} are: {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}. Their minimal values are 1, 1, 1, 2, 2, 3. So the average (expected) value is F(4,2)=(1+1+1+2+2+3)/6=10/6=1.66666666

可得两个结论：

F(n,k)>F(nm,k)   n>m

F(n,k)>F(n,p)   k<p

所以a中最小的数对应b中最大的数，依次递推

code：

#include<stdio.h>
#include<algorithm>
using namespace std;
int a[200005],b[200005];
struct node{
        int x,pos;
}q[200005];
int cmp(node t1,node t2){
        return t1.x>t2.x;
}
int main(){
        int n,i;
        while(~scanf("%d",&n)){
                for(i=0;i<n;i++) scanf("%d",&a[i]);
                for(i=0;i<n;i++){
                        scanf("%d",&q[i].x);
                        q[i].pos=i;
                }
                sort(a,a+n);
                sort(q,q+n,cmp);
                for(i=0;i<n;i++){
                        b[q[i].pos]=a[i];
                }
                for(i=0;i<n;i++) printf("%d%c",b[i],i==n?'\n':' ');
        }
        return 0;
}