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> 
#include<cmath>
#include<string>
#define pb push_back
#define x first
#define y second
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define all(x) x.begin(),x.end()
#define int long long
#define ll long long
using namespace std;
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
//void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
// look for  all edge cases
//search for a pattern




void solve(){
	int n;
	cin >> n;
	vector<int> v(n);
	for(int i=0; i<n; i++){
		cin >> v[i];
	}
	//vector<int> new_v = sort(all(v));
	
	vector<int> fixed(n, -1), min_v(n, -1), max_v(n, -1);
	fixed[0] = v[0];
	set<int> c;
	vector<int> volf;
	volf.pb(v[0]);
	c.insert(v[0]);
	for(int i =1; i<n; i++){
		if(v[i-1] != v[i]){
			fixed[i] = v[i];
			c.insert(v[i]);
			volf.pb(v[i]);
		}
	}
	
	//set<int> covered;
	
	int now = 1;
	
	//if(v[0] == 1){
		//now += 1;
	//}
	
	for(int i =0; i<n; i++){
		if(fixed[i] == -1){
			while(c.find(now) != c.end()){
				now += 1;
			}
			min_v[i] = now;
			c.insert(now);
			now += 1;
		}
		else{
			min_v[i] = fixed[i];
			//max_v[i] = fixed[i];
		}
	}
	
	
	//debug(volf);
	int idx = 1;
	stack<int> s;
	for(int i = 1; i < v[0]; i++){
		s.push(i);
	}
	//if((int)volf.size() > 1){
		//for(int i=v[0]+1; i < volf[1]; i++){
			//s.push(i);
		//}
	//}
	max_v[0] = fixed[0];
	for(int i=1; i<n; i++){
		if(fixed[i] == -1){
			max_v[i] = s.top();
			s.pop();
		}
		else{
			max_v[i] = fixed[i];
			//max_v[i] = fixed[i];
			if(idx < (int)volf.size()){
				//debug(idx);
				for(int j = volf[idx-1]+1; j< volf[idx]; j++){
					s.push(j);
				}
				idx += 1;
			}
		}
	}
	
	for(auto it : min_v){
		cout << it << " ";
	}
	cout << "\n";
	for(auto it : max_v){
		cout << it << " ";
	}
	cout << "\n";
	
	
}


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);	
	
	int t;
	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
	
}