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;
//#include <ext/pb_ds/assoc_container.hpp> // Common file 
//#include <ext/pb_ds/tree_policy.hpp> 
//#include <functional> // for less 
//using namespace __gnu_pbds; 
// GNU link : https://goo.gl/WVDL6g 
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> new_data_set;
//insert(key) , *p.find_by_order(key), p.order_of_key(key),  
//#include <boost/range/adaptor/reversed.hpp> //for (auto i : boost::adaptors::reverse(mpp))
#define int long long
#define get1(x) int x; cin>>x
#define dbg(x) cout<<#x<<":"<<x<<endl;
#define dbg1(x) cout<<x<<endl;
#define dbg2(a,b) cout<<a<<" "<<b<<endl
#define dbg3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define dbg4(a,b,c,d) cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl
#define min2(x,y) (x<y?x:y)
#define max2(x,y) (x>y?x:y)
#define MOD 1000000007
#define set0(x) memset(x,0,sizeof(x))
#define rep(i,a,b) for(int i=a; i<b; i++)
#define repR(i,a,b) for(int i=b; i>=a; i--)
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
#define sz(v) v.size()
#define all(v)    v.begin(),v.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define PI 3.1415926535897932384626
#define f first
#define s second
#define vi vector<int>
#define vb vector<bool>
#define vi2(brr,n,m,val) vector<vector<int>>  brr(n, vector<int> (m,val))
#define vb2(brr,n,m,val) vector<vector<bool>> brr(n, vector<bool>(m,val))
#define vii vector<pii>
#define modInv(b,m) power(b,m-2,m)
#define modDiv(a,b,m) (power(b,m-2,m)*a)%m
int gcd(int a , int b){ if(b==0) return a;  a%=b; return gcd(b,a); } 
int power(int x,int y, int md=MOD){int res = 1;x%=md;while(y>0){if(y&1)res = (res*x)%md;x = (x*x)%md;y = y>>1;}return res%md;}
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b) { return (a.second < b.second);} 
// Aditya/.config/sublime-text-3/Packages/User
//floor(a/b) = a/b
//ceil(a/b) = (a+b-1)/b

void solve(){
	get1(n);
	
	vector<int> arr(n), brr(n,0), crr(n,0);

	rep(i,0,n) {
		cin>>arr[i];
		if(i==0) {
			brr[i] = arr[i];
			crr[i] = arr[i];
			continue;
		}
		if(arr[i] != arr[i-1]) {
			brr[i] = arr[i];
			crr[i] = arr[i];
			continue;
		}
	}


	set<int> stt, stt2;
	rep(i,1,n+1) {
		stt.insert(i);
		stt2.insert(i);
	}
	rep(i,0,n) {
		stt.erase(brr[i]);
		stt2.erase(brr[i]);
	}

	// min
	rep(i,0,n) {
		if(brr[i] != 0) continue;
		int x = *stt.begin();
		brr[i] = x;
		stt.erase(x);
	}
	rep(i,0,n) cout<<brr[i]<<" "; cout<<endl;

	//max
	int mx = 0;
	rep(i,0,n) {
		mx = max2(mx, arr[i]);
		if(crr[i] != 0) continue;
		auto itr = stt2.lower_bound(mx);
		itr--;
		int x = *itr;
		crr[i] = x;
		stt2.erase(x);
	}
	rep(i,0,n) cout<<crr[i]<<" "; cout<<endl;

	return;
}

int32_t main(){
	boost;
//	#ifndef ONLINE_JUDGE
//		freopen("input.txt", "r", stdin);
//		freopen("output.txt", "w", stdout);
//	#endif // ONLINE_JUDGE
	
	get1(t);
	rep(testcaseNum,1,t+1) {
//		cout<<"Case #"<<testcaseNum<<" ";
		solve();
	}
		
	return 0;
}