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;

#pragma GCC optimize("O3")
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define ll long long
#define PI 3.1415926535897932384626
#define endl '\n'
#define FIO                           \
	freopen("input.txt", "r", stdin); \
	freopen("output.txt", "w", stdout);
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define clr(x) memset(x, 0, sizeof(x))
#define tr(it, x) for (auto it = x.begin(); it != x.end(); it++)
#define trr(it, x) for (auto it = x.rbegin(); it != x.rend(); it++)

#define umin(...) min({__VA_ARGS__})
#define umax(...) max({__VA_ARGS__})
#define MAX(v) *max_element(all(v))
#define MIN(v) *min_element(all(v))

typedef pair<ll, ll> pl;
typedef vector<ll> vl;
typedef vector<pl> vpl;
typedef vector<vl> vvl;
const int MOD = 1000000007;
const int INF = 1000000009;
const int MAXN = 1000005;  //300050;

/*debugging */
vector<string> split(const string& s, char c) {
	vector<string> v;
	stringstream ss(s);
	string x;
	while (getline(ss, x, c)) v.emplace_back(x);
	return move(v);
}
template <typename T, typename... Args>
inline string arrStr(T arr, int n) {
	stringstream s;
	s << "[";
	for (int i = 0; i < n - 1; i++) s << arr[i] << ",";
	s << arr[n - 1] << "]";
	return s.str();
}

#ifndef ONLINE_JUDGE
#define debug(args...)                            \
	{                                             \
		__evars_begin(__LINE__);                  \
		__evars(split(#args, ',').begin(), args); \
	}

inline void __evars_begin(int line) { cerr << "#" << line << ": "; }
template <typename T>
inline void __evars_out_var(vector<T> val) { cerr << arrStr(val, val.size()); }
template <typename T>
inline void __evars_out_var(T* val) { cerr << arrStr(val, 10); }
template <typename T>
inline void __evars_out_var(T val) { cerr << val; }
inline void __evars(vector<string>::iterator it) { cerr << endl; }

template <typename T, typename... Args>
inline void __evars(vector<string>::iterator it, T a, Args... args) {
	cerr << it->substr((*it)[0] == ' ', it->length()) << "=";
	__evars_out_var(a);
	cerr << "; ";
	__evars(++it, args...);
}
// #define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif


/* Function to check primality in O(sqrt(n)) */
bool check_prime(ll n) {
	if (n < 2)
		return false;
	for (ll x = 2; x * x <= n; x++) {
		if (n % x == 0)
			return false;
	}
	return true;
}

/* Function to get prime factorization of n in O(sqrt(n))*/
vector<ll> get_prime_factors(ll n) {
	vector<ll> f;
	for (ll x = 2; x * x <= n; x++) {
		while (n % x == 0) {
			f.push_back(x);
			n /= x;
		}
	}
	if (n > 1)
		f.push_back(n);
	return f;
}


ll fpow(ll x, ll n) {
	ll res = 1;
	while (n) {
		if (n & 1) {
			res = (1LL * res * x) % MOD;
		}
		x = (1LL * x * x) % MOD;
		n >>= 1;
	}
	return (res % MOD);
}

vector<ll> fac, inv;
void create_fac(ll n = MAXN) {
	fac.resize(n + 5);
	inv.resize(n + 5);
	fac[0] = 1;
	inv[0] = fpow(fac[0], MOD - 2);
	for (ll i = 1; i <= n; i++) {
		fac[i] = (fac[i - 1] % MOD * i % MOD) % MOD;
		inv[i] = fpow(fac[i], MOD - 2);
	}
}

ll binomial_coefficient(ll n, ll r) {
	ll res = 1;
	res = (res * (fac[n] % MOD)) % MOD;
	res = (res * (inv[r] % MOD)) % MOD;
	res = (res * (inv[n - r] % MOD)) % MOD;
	// res = (res, ) % MOD;
	return res;
}

ll gcd(ll a, ll b) {
	if (b == 0)
		return a;
	return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
	return a * (b / gcd(a, b));
}

ll sceil(ll a, ll b) {
	return (a + b - 1) / b;
}

vector<ll> lp;
vector<ll> pr;
void sieve(ll n = MAXN) {
	lp.resize(n + 1);
	lp.clear();
	for (ll i = 2; i <= n; ++i) {
		if (lp[i] == 0) {
			lp[i] = i;
			pr.push_back(i);
		}
		for (ll j = 0; j < (ll)pr.size() && pr[j] <= lp[i] && i * pr[j] <= n; ++j)
			lp[i * pr[j]] = pr[j];
	}
}

/* ========== YOUR CODE HERE ========= */

void solution() {
	// ll solution() {
	ll n = 0;
	cin >> n;

	ll a[n];
	for (ll i = 0; i < n; i++)
		cin >> a[i];

	ll mx[n], mn[n];
	memset(mx, 0, sizeof(mx));
	memset(mn, 0, sizeof(mn));

	mx[0] = mn[0] = a[0];

	set<ll> s;
	s.insert(a[0]);

	for (ll i = 1; i < n; i++) {
		if (a[i] != a[i - 1]) {
			mx[i] = mn[i] = a[i];
			s.insert(a[i]);
		}
	}

	ll id = 1;

	// for(auto i = s.begin(); i != s.end(); i++)
	// 	cout << *i << ' ';
	// 	cout<<endl;

	for (ll i = 0; i < n; i++) {
		if (!mn[i]) {
			while (id < n && s.find(id) != s.end()) {
				id++;
			}
			mn[i] = id;
			// cout << "ID" << mn[i] << endl;
			id++;
		}
	}

	ll prev = 1;
	// id = -(a[0] - 1);

	s.clear();
	// for (int i = 0; i < n; i++) {
	// 	if (mx[i]) {
	// 		s.insert(-mx[i]);
	// 	}
	// }

	for (ll i = 0; i < n; i++) {
		for (int j = prev; j <= a[i]; j++)
			s.insert(j);

		prev = a[i] + 1;

		mx[i] = *s.rbegin();
		s.erase(*s.rbegin());
	}

	//output
	for (ll i = 0; i < n; i++)
		cout << mn[i] << ' ';
	cout << endl;
	for (ll i = 0; i < n; i++)
		cout << mx[i] << ' ';
	cout << endl;
}

/* ========== YOUR CODE HERE ========= */

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int t = 1;
	cin >> t;
	while (t--) {
		// cout << solution() << endl;
		solution();
	}

	return 0;
}