Kolya has a turtle and a field of size 2 × n. The field rows are numbered from 1 to 2 from top to bottom, while the columns are numbered from 1 to n from left to right.

Suppose in each cell of the field there is a lettuce leaf. The energy value of lettuce leaf in row i and column j is equal to a_{i,j}. The turtle is initially in the top left cell and wants to reach the bottom right cell. The turtle can only move right and down and among all possible ways it will choose a way, maximizing the total energy value of lettuce leaves (in case there are several such paths, it will choose any of them).

Kolya is afraid, that if turtle will eat too much lettuce, it can be bad for its health. So he wants to reorder lettuce leaves in the field, so that the energetic cost of leaves eaten by turtle will be minimized.

Input

The first line contains an integer n (2 ≤ n ≤ 25) — the length of the field.

The second line contains n integers a_{1, i} (0 ≤ a_{1, i} ≤ 50 000), the energetic cost of lettuce leaves in the first row of the field.

The third line contains n integers a_{2, i} (0 ≤ a_{2, i} ≤ 50 000), the energetic cost of lettuce leaves in the second row of the field.

Output

Print two lines with n integers in each — the optimal reordering of lettuce from the input data.

In case there are several optimal ways to reorder lettuce, print any of them.

Examples

Input


2
1 4
2 3


Output


1 3 
4 2 


Input


3
0 0 0
0 0 0


Output


0 0 0 
0 0 0 


Input


3
1 0 1
0 0 0


Output


0 0 1
0 1 0

Note

In the first example, after reordering, the turtle will eat lettuce with total energetic cost 1+4+2 = 7.

In the second example, the turtle will eat lettuce with energetic cost equal 0.

In the third example, after reordering, the turtle will eat lettuce with total energetic cost equal 1.
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define FAST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DECIMAL(n)  std::cout << std::fixed;std::cout << std::setprecision(n);
#define hell 1000000007
#define narak 998244353
#define PI 3.14159265358979323844
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define fi first 
#define se second
#define all(v) v.begin(), v.end()
#define endl "\n"
#define sqr(a) (a)*(a)
#define __lcm(m,n) m*(n/__gcd(m,n))
#define inputarr(a,n) for(int xxx=0;xxx<n;++xxx) cin>>(a)[xxx]
#define sz(a) (int)a.size()
#define sl(a) (int)a.length()
#define display(x) for(auto &a:x) cout<<a<<" ";cout<<endl
#define debug cerr<<"bhau"<<endl
#define between(n,a,b) (a<=n&&n<=b)
#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC 

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}


template<typename T, typename U> static inline void amin(T &x, U y) { 
    if (y < x) 
        x = y; 
}

template<typename T, typename U> static inline void amax(T &x, U y) { 
    if (x < y) 
        x = y; 
}

template<typename T,typename U> std::ostream& operator<<(std::ostream& out, std::pair<T,U> a) {
    out<<a.fi<<" "<<a.se;
    return out;
}

template<typename T,typename U> std::istream& operator>>(std::istream& in, std::pair<T,U> &a) {
    in>>a.fi>>a.se;
    return in;
}

inline long long toint(const std::string &s) {std::stringstream ss; ss << s; long long x; ss >> x; return x;}
inline std::string tostring(long long number) {std::stringstream ss; ss << number; return ss.str();}
inline std::string tobin(long long x) {return std::bitset<63>(x).to_string();}

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

#define ll long long
#define pii std::pair<int, int>
#define vi vector<int>  
#define vvi vector<vi > 
#define vii vector<pii >
#define point complex<ll>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//primes for hashing 937,991,1013,1409,1741

using namespace std;
using namespace __gnu_pbds;

bitset<2400001> dp[50][25];
void meowmeow321()
{
    int n;
    cin>>n;
    vi kitty(2*n);
    inputarr(kitty,2*n);
    int s=accumulate(all(kitty),0);
    sort(all(kitty),greater<int>());
    vi row1,row2;
    row1.pb(kitty.back());
    kitty.pop_back();
    row2.pb(kitty.back());
    kitty.pop_back();
    n=sz(kitty);
    dp[0][0][0]=1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= n/2; ++j) {
            dp[i+1][j]|=dp[i][j];
            if(j<n/2)
                dp[i+1][j+1]|=(dp[i][j]<<kitty[i]);
        }
    }
    int aval,ans=hell;
    for (int i = 0; i < 2400001; ++i) {
        if(dp[n][n/2][i]){
            int wen=abs(s-2*row1[0]-2*i);
            if(wen<ans){
                ans=wen;
                aval=i;
            }
        }
    }
    int cur=n;
    while(sz(row1)<n/2 +1){
        cur--;
        if(aval>=kitty[cur]&&dp[cur][n/2-sz(row1)][aval-kitty[cur]]){
            row1.pb(kitty[cur]);
            aval-=kitty[cur];
        }else row2.pb(kitty[cur]);
    }
    while(cur>0){
        cur--;
        row2.pb(kitty[cur]);  
    }
    sort(all(row1));
    display(row1);
    sort(all(row2));
    reverse(all(row2));
    display(row2);
}
signed main()
{
    FAST;
    int testcases=1;
    //cin>>testcases;
    for(int i=0;i<testcases;++i)
    {
        meowmeow321();
    }
    cerr<<endl<<"Time Elasped : "<<elasped_time<<endl;
    return 0;
}