Problem: A permutation is a sequence of n integers from 1 to n, in which all numbers occur exactly once. For example, [1], [3, 5, 2, 1, 4], [1, 3, 2] are permutations, and [2, 3, 2], [4, 3, 1], [0] are not.

Polycarp was presented with a permutation p of numbers from 1 to n. However, when Polycarp came home, he noticed that in his pocket, the permutation p had turned into an array q according to the following rule: 

  * q_i = max(p_1, p_2, …, p_i). 



Now Polycarp wondered what lexicographically minimal and lexicographically maximal permutations could be presented to him.

An array a of length n is lexicographically smaller than an array b of length n if there is an index i (1 ≤ i ≤ n) such that the first i-1 elements of arrays a and b are the same, and the i-th element of the array a is less than the i-th element of the array b. For example, the array a=[1, 3, 2, 3] is lexicographically smaller than the array b=[1, 3, 4, 2].

For example, if n=7 and p=[3, 2, 4, 1, 7, 5, 6], then q=[3, 3, 4, 4, 7, 7, 7] and the following permutations could have been as p initially: 

  * [3, 1, 4, 2, 7, 5, 6] (lexicographically minimal permutation); 
  * [3, 1, 4, 2, 7, 6, 5]; 
  * [3, 2, 4, 1, 7, 5, 6]; 
  * [3, 2, 4, 1, 7, 6, 5] (lexicographically maximum permutation). 



For a given array q, find the lexicographically minimal and lexicographically maximal permutations that could have been originally presented to Polycarp.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5).

The second line of each test case contains n integers q_1, q_2, …, q_n (1 ≤ q_i ≤ n).

It is guaranteed that the array q was obtained by applying the rule from the statement to some permutation p.

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case, output two lines: 

  * on the first line output n integers — lexicographically minimal permutation that could have been originally presented to Polycarp; 
  * on the second line print n integers — lexicographically maximal permutation that could have been originally presented to Polycarp; 

Example

Input


4
7
3 3 4 4 7 7 7
4
1 2 3 4
7
3 4 5 5 5 7 7
1
1


Output


3 1 4 2 7 5 6 
3 2 4 1 7 6 5 
1 2 3 4 
1 2 3 4 
3 4 5 1 2 7 6 
3 4 5 2 1 7 6 
1 
1 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std ;
 
#define ll              long long  
#define ld              long double
#define pll             pair<ll,ll>
#define pb              push_back
#define all(v)          begin(v), end(v)
#define sz(a)           (ll)a.size()
#define F               first
#define S               second
#define INF             2000000000000000000
#define endl            "\n"
#define mem0(x)         memset(x, 0, sizeof(x))
#define mem1(x)         memset(x, -1, sizeof(x))
#define rep(i,k,n)      for (ll i = k; i <= n; ++i) 
#define repr(i,k,n)     for (ll i = k; i >= n; --i)
#define br              cout<<"\n";
 
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> void read(T &p){cin >> p;}
template <typename T, typename T1> void read(pair<T, T1> &p){read(p.F);read(p.S);}
template <typename T> void read(T arr[], ll n){for (ll i = 0; i < n; i++) read(arr[i]);}
template <typename T> void read(vector<T> &arr){for (ll i = 0; i < arr.size(); i++)read(arr[i]);}
 
template <typename T> void print(T &n){cout << n;} 
template <typename T, typename T1>void print(pair<T, T1> &p){print(p.F);cout<<" ";print(p.S);}
template <typename T>void print(T arr[], ll n){for (ll i = 0; i < n; i++){print(arr[i]);cout<< " ";}}
template <typename T>void print(vector<T> &arr){for (ll i = 0; i < arr.size(); i++){print(arr[i]);cout<<" ";}}
template <typename T>void print(set<T> &arr){for (auto i : arr){ print(i); cout<< " ";}}
template <typename T>void print(multiset<T> &arr){for (auto i : arr){print(i);cout<< " ";}}
template <typename T, typename T1> void print(map<T, T1> &m){for (auto i : m){print(i.F);cout<<" -> ";print(i.S); br;}}
 
void solve(){
    
    ll n;
    cin>>n; 

    ll mn[n], mx[n], u[n+1], u1[n+1], p1 = 1, ar[n]; 
    mem0(u); 
    mem0(u1);
    mem0(mx);  
    set<ll> st; 

    rep(i, 0, n-1){
    	cin>>ar[i]; 
    	ll t = ar[i];

    	if(u[t]){
    		while(u[p1])
    			p1++; 
    		mn[i] = p1; 
    		p1++; 
    	}else{
    		mn[i] = t; 
    		mx[i] = t; 
    		u[t]++;
    		u1[t]++;  
    	}

    	st.insert(-(i+1)); 
    }


    rep(i, 0, n-1){
    	if(mx[i]){
    		// ll t = mx[i]-1; 
    		// i++; 
			auto it = st.find(-mx[i]);
			vector<ll> del;
			del.pb(-mx[i]);
			it++; 

			// cout<<"MX[i] = "<<mx[i]<<" i = "<<i<<endl;
			i++;
			for(auto t = it; it != st.end() and mx[i]==0; it++){
				mx[i] = -(*it);
				del.pb(*it);
				i++;
			}

			for(auto x: del){
				// cout<<x<<" "; 
				st.erase(st.find(x)); 
			}
    		
    		i--; 
    	}


    }

    print(mn, n); 
    br;
    print(mx, n); 
    br;
}
 
 
int main()
{ 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 
    int test = 1; 
    cin>>test;
    while(test--){
        solve(); 
    }
 
    return 0; 
}