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 JAVA):

Solution:
import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
public class pcarp{
	static int max_value;
	static long mod = (long)1e9+7;
	static long ans = (long)1e15;
	static int ans1;
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int t = sc.nextInt();
		while(t-->0){
			int n = sc.nextInt();
			int[] arr = new int[n];
			TreeSet<Integer> min = new TreeSet<>();
			TreeSet<Integer> max = new TreeSet<>();
			for(int i=0;i<n;i++){
				arr[i]=sc.nextInt();
				min.add(i+1);
				max.add(i+1);
			}
			int prev=0;
			int[] mn = new int[n];
			int[] mx = new int[n];
			for(int i=0;i<n;i++){
				if(prev!=arr[i]){
					mn[i]=arr[i];
					mx[i]=arr[i];
					min.remove(arr[i]);
					max.remove(arr[i]);
				}
				else{
					mn[i]=min.pollFirst();
					mx[i]=max.floor(arr[i]);
					max.remove(max.floor(arr[i]));
				}
				prev=arr[i];
			}
			for(int i=0;i<n;i++){
				System.out.print(mn[i]+" ");
			}
			System.out.println();
			for(int i=0;i<n;i++){
				System.out.print(mx[i]+" ");
			}
			System.out.println();
		}
	}
	 public static void reverse(int[] arr, int i, int j){
    	int left = i;
    	int right = j;
    	int temp;
    	while (left < right)
            {
                temp=arr[left];
                arr[left]=arr[right];
                arr[right]=temp;
                left+=1;
                right-=1;
            }
    }
	static int recusive(String str, int x, int y, int pos, char prev,HashMap<String,Integer> map)
	{
		String s = Integer.toString(pos)+"$"+prev;
		if(pos == str.length())
			return 0;
		if(map.containsKey(s)){
			return map.get(s);
		}
		if (str.charAt(pos) == 'C')
		{
			if(prev == 'C'){
				int a =recusive(str, x, y, pos+1, 'C',map);
				map.put(s,a);
				return a;
			}
			else{
				int a = y + recusive(str, x, y, pos+1, 'C',map);
				map.put(s,a);
				return a;
			}
		}
		
		else if (str.charAt(pos) == 'J'){
			if(prev == 'C'){

				int a = x + recusive(str, x, y, pos+1, 'J',map);
				map.put(s,a);
				return a;
			}
			else{
				int a= recusive(str, x, y, pos+1, 'J',map);
				map.put(s,a);
				return a;
			}
			
		}
		int op1 = Integer.MAX_VALUE/2;
		int op2 = Integer.MAX_VALUE/2;
		if(prev == 'C')
		{ 
			op1 = recusive(str, x, y, pos+1, 'C',map);
			op2 = x + recusive(str, x, y, pos+1, 'J',map);
			
		}else {
			op1 = y + recusive(str, x, y, pos+1, 'C',map);
			op2 = recusive(str, x, y, pos+1, 'J',map);
		}
		int b =Math.min(op1, op2);
		map.put(s,b);
		return b;
	}
	public static int f_min(String s, int i, int x, int y){
		if(i==s.length()-1){
			return 0;
		}
		if(s.charAt(i)=='C' || s.charAt(i)=='J'){
			if(i+1<s.length() && s.charAt(i)=='C' && s.charAt(i+1)=='J'){
				return x+f_min(s,i+1,x,y);
			}
			if(i+1<s.length() && s.charAt(i)=='J' && s.charAt(i+1)=='C'){
				return y+f_min(s,i+1,x,y);
			}
			else{
				return f_min(s,i+1,x,y);
			}
		}
		else {
			return Math.min((i-1>=0 && s.charAt(i-1)=='J')?y:0+(s.charAt(i+1)=='J'?x:0)+f_min(s.substring(0,i)+"C"+s.substring(i+1,s.length()),i+1,x,y),(i-1>=0 && s.charAt(i-1)=='C')?x:0+(s.charAt(i+1)=='C'?y:0)+f_min(s.substring(0,i)+"J"+s.substring(i+1,s.length()),i+1,x,y));
		}
	}
	public static int minf(int[] arr, int i, int j){
        int minidx=-1;
        int min=Integer.MAX_VALUE;
        for(int p=i;p<=j;p++){
            if(arr[p]<min){
                min=arr[p];
                minidx=p;
            }
        }
        return minidx;
    }
  
	public static int fstr(String s1, String s2, HashMap<String,Integer> map){
		String s = s1+"$"+s2;
		if((s1.length()==0 && s2.length()!=0)||(s1.length()!=0 && s2.length()==0)){
			return 1000;
		}

		if(s1.equals(s2)){
			return 0;
		}
		if(map.containsKey(s)){
			return map.get(s);
		}
		int p =1+Math.min(fstr(s1,s2.substring(1,s2.length()),map),Math.min(fstr(s1,s2.substring(0,s2.length()-1),map),(Math.min(fstr(s1.substring(1,s1.length()),s2,map),fstr(s1.substring(0,s1.length()-1),s2,map)))));
		map.put(s,p);
		return p;
	}


	public static int binarySearch(Point[] arr, int i){
		int lo=0;
		int hi = arr.length-1;
		while(lo<=hi){
			int mid = lo+(hi-lo)/2;
			if(arr[mid].end<arr[i].start){
				if(arr[mid+1].end<arr[i].start){
					lo=mid+1;
				}
				else{
					return mid;
				}
			}
			else{
				hi = mid-1;
			}
		}
		return -1;
	}
	public static boolean fbool(int[][] a, int[][] b,int r, int c){
		for(int i=0;i<r;i++){
			for(int j=0;j<c;j++){
				if(a[i][j]!=b[i][j]){
					return false;
				}
			}
		}
		return true;
	}
	public static long fmin(long n, long a, long b, long c, long e, long h){
		if(n<=0){
			return 0;
		}
		if(n<=e && n<=h){
			ans=Math.min(ans,n*c);
		}
		if(2*n<=e){
			ans=Math.min(ans,n*a);
		}
		if(3*n<=h){
			ans=Math.min(ans,n*b);
		}
		if((h-n)/2>=1 && (h-n)/2>=(n-e)){
			if(b<c){
				long k=Math.min(n-1,(h-n)/2);
				ans=Math.min(ans,(b-c)*k+n*c);
			}
			else{
				long k=Math.max(1,n-e);
				ans=Math.min(ans,(b-c)*k+n*c);
			}
		}
		if((e-n)>=1 && (e-n)>=(n-h)){
			if(a<c){
				long k=Math.min(n-1,(e-n));
				ans=Math.min(ans,(a-c)*k+n*c);
			}
			else{
				long k=Math.max(1,n-h);
				ans=Math.min(ans,(a-c)*k+n*c);
			}
		}
		if(e/2>=1 && e/2>=(3*n-h+2)/3){
			if(a<b){
				long k=Math.min(n-1,e/2);
				ans=Math.min(ans,(a-b)*k+n*b);
			}
			else{
				long k=Math.max(1,(3*n-h+2)/3);
				ans=Math.min(ans,(a-b)*k+n*b);
			}
		}
		if(e>=3 && h>=4 && n>=3){
			ans=Math.min(ans,(a+b+c)+fmin(n-3,a,b,c,e-3,h-4));
		}
		return ans;
	}
	public static ArrayList<Integer> digits(int n){
		ArrayList<Integer> arr = new ArrayList<>();
		while(n>0){
			arr.add(n%10);
			n/=10;
		}
		return arr;
	}
	public static void precompute(){
		for(int i=0;i<=1e5;i++){

		}
	}
	public static boolean valid(String s){
		Stack<Character> st  = new Stack<>();
		for(int i=0;i<s.length();i++){
			if(st.isEmpty() || s.charAt(i)=='('){
				st.push(s.charAt(i));
			}
			else if(st.peek()=='(' && s.charAt(i)==')'){
				st.pop();
			}
		}
		if(st.isEmpty()){
			return true;
		}
		return false;
	}
	public static int minswap(int[] A, int[] B, boolean swap, int pos, int n){
		if(pos>=n){
			return 0;
		}
		int prev_a = swap==true?B[pos-1]:A[pos-1];
		int prev_b = swap==true?A[pos-1]:B[pos-1];
		int ans=Integer.MAX_VALUE;
		if(prev_a<=A[pos] && prev_b<=B[pos]){
			ans=Math.min(ans,minswap(A,B,false,pos+1,n));
		}
		if(prev_a<=B[pos] && prev_b<=A[pos]){
			ans=Math.min(ans,1+minswap(A,B,true,pos+1,n));
		}
		return ans;
	}
	public static int lcs(int[] arr, int n, int pos, int last, HashMap<Integer,Integer> map){
			return 0;
	}

	public static int bg(int n, int pos, char last){

			return 0;
	}
    public static int maxheight(int[] arr, int n){
    	int[] right = new int[n];
    	int[] left= new int[n];
    	Stack<Integer> st = new Stack<>();
    	for(int i=0;i<n;i++){
    		while(!st.isEmpty() && arr[i]<arr[st.peek()]){
    			right[st.pop()]=i;
    		}
    		st.push(i);
    	}
    	while(!st.isEmpty()){
    		right[st.pop()]=n;
    	}
    	for(int i=n-1;i>=0;i--){
    		while(!st.isEmpty() && arr[i]<arr[st.peek()]){
    			left[st.pop()]=i;
    		}
    		st.push(i);
    	}
    	while(!st.isEmpty()){
    		left[st.pop()]=-1;
    	}
    	int max=0;
    	for(int i=0;i<n;i++){
    		max=Math.max(max,arr[i]*(right[i]-left[i]-1));
    	}
    	return max;

    }
    public static void show(int[] arr){
    	int n = arr.length;
    	for(int i=0;i<n;i++){
    		System.out.print(arr[i]+" ");
    	}
    	System.out.println();
    }
	public static String pd(String s){
		int start=0;
		int maxLength=1;
		int low,high;

		for(int i=1;i<s.length();i++){
			low=i-1;
			high=i;
			while(low>=0 && high<s.length() && s.charAt(low)==s.charAt(high)){
				if(high-low+1>maxLength){
					start=low;
					maxLength=high-low+1;
				}
				low--;
				high++;
			}
			low=i-1;
			high=i+1;
			while(low>=0 && high<s.length() && s.charAt(low)==s.charAt(high)){
				if(high-low+1>maxLength){
					start=low;
					maxLength=high-low+1;
				}
				low--;
				high++;
			}
		}
		return s.substring(start,start+maxLength);
		// return String[]{s.substring(start,start+maxLength),s.substring(0,start)+s.substring(start+maxLength,s.length())};
	}

	static boolean isPrime1(int n)  
    {   
        if (n <= 1) return false;  
        if (n <= 3) return true;  
          
        if (n % 2 == 0 || n % 3 == 0) return false;  
          
        for (int i = 5; i * i <= n; i = i + 6)  
            if (n % i == 0 || n % (i + 2) == 0)  
            return false;  
          
        return true;  
    }  
        
    static int nextPrime(int N)  
    {  
      
          
        if (N <= 1)  
            return 2;  
      
        int prime = N;  
        boolean found = false;  
     
        while (!found)  
        {  
            prime++;  
      
            if (isPrime1(prime))  
                found = true;  
        }  
        return prime;  
    }

	

	public static int robber_house(int[] arr, int pos, int n, int[] dp){
		if(pos>=n){
			return 0;
		}
		if(dp[pos]!=-1){
			return dp[pos];
		}
		return dp[pos]=Math.max(arr[pos]+robber_house(arr,pos+2,n,dp),robber_house(arr,pos+1,n,dp));
	}

	// public static long[] djk(int start,HashMap<Integer,List<Point>> map, int size ){
	// 	Queue<Point> q1 = new PriorityQueue<>();
	// 	long[] minCost = new long[size+1];
	// 	boolean[] isVisited = new boolean[size+1];
	// 	Arrays.fill(minCost,Long.MAX_VALUE);
	// 	minCost[start]=0;
	// 	isVisited[start]=true;
	// 	if(!map.containsKey(start)){
	// 		return minCost;
	// 	}
	// 	q1.addAll(map.get(start));
	// 	while(!q1.isEmpty()){
	// 		Point p = q1.poll();
	// 		if(isVisited[p.getKey()]){
	// 			continue;
	// 		}
	// 		isVisited[p.getKey()]=true;
	// 		minCost[p.getKey()]=p.getValue();
	// 		for(Point q : map.get(p.getKey())){
	// 			long nextVal=0;
	// 			if(isVisited[q.getKey()]){
	// 				continue;
	// 			}
	// 			if(minCost[p.getKey()]%q.getK()==0){
	// 				nextVal=minCost[p.getKey()]+q.getValue();
	// 			}
	// 			else{
	// 				nextVal=minCost[p.getKey()]+(q.getK()-minCost[p.getKey()]%q.getK())+q.getValue();
	// 			}
	// 			if(minCost[q.getKey()]>nextVal){
	// 				minCost[q.getKey()]=nextVal;
	// 				q1.add(new Point(q.getKey(),nextVal,q.getK()));
	// 			}
	// 		}
	// 	}
	// 	return minCost;
	// }

	public static void permutation(char[] arr, int j){
		if(j==arr.length-1){
			print(arr);
			System.out.println();
		}
		for(int i=j;i<arr.length;i++){
			char temp = arr[i];
			arr[i]=arr[j];
			arr[j]=temp;
			permutation(arr,j+1);
			char temp1 = arr[i];
			arr[i]=arr[j];
			arr[j]=temp1;
		}
	}

	public static void print(char[] arr){
		for(char c : arr){
			System.out.print(c);
		}
	}

	public static long inc(String s){
		char[] arr = s.toCharArray();
		Arrays.sort(arr);
		String ans="";
		for(int i=0;i<s.length();i++){
			ans+=arr[i];
		}
		return Long.parseLong(ans);
	}

	public static long dec(String s){
		char[] arr = s.toCharArray();
		Arrays.sort(arr);
		String ans="";
		for(int i=s.length()-1;i>=0;i--){
			ans+=arr[i];
		}
		return Long.parseLong(ans);
	}
	public static long max(String n){
		long max=0;
		for(int i=0;i<n.length();i++){
			if(n.charAt(i)-'0'>max){
				max=n.charAt(i)-'0';
			}
		}
		return max;
	}

	public static long base(String n, long b){
		long ans=0;
		for(int i=0;i<n.length();i++){
			ans+=power(b,(long)(n.length()-1-i))*(n.charAt(i)-'0');
		}
		return ans;
	}

	public static long power(long a, long b){
		long res=1;
		while(b>0){
			if((b&1)==1){
				res=res*a;
			}
			b=b>>1;
			a=a*a;
		}
		return res;
	}

	public static long value(int[] arr){
		Arrays.sort(arr);
		return arr[arr.length/2]-arr[(arr.length-1)/2]+1;
	}

	static void function(int l, int r, int[] arr, int[] depth, int d){
		if(r<l){
			return;
		}
		if(r==l){
			depth[l]=d;
			return;
		}
		int m = l;
		for(int i=l+1;i<=r;i++){
			if(arr[m]<arr[i]){
				m=i;
			}
		}
		depth[m]=d;
		function(l,m-1,arr,depth,d+1);
		function(m+1,r,arr,depth,d+1);
	}

	static boolean perfectCube(long N)
    {
        long cube_root;
        cube_root = (long)Math.round(Math.cbrt(N));
     
        // If cube of cube_root is equals to N,
        // then print Yes Else print No
        if (cube_root * cube_root * cube_root == N) {
            return true;
        }
        return false;
    }

	public static int value(int n){
		if(n==0){
			return 0;
		}
		int cnt=0;
		while(n>0){
			cnt++;
			n/=2;
		}
		return cnt;
	}

	public static int value1(int n){
		int cnt=0;
		while(n>1){
			cnt++;
			n/=2;
		}
		return cnt;
	}

	public static String function(String s){

		if(check(s)){
			return s;
		}
		if(s.length()==2 && s.charAt(0)==s.charAt(1)){
			return "";
		}
		if(s.charAt(0)==s.charAt(1)){
			return function(s.substring(2,s.length()));
		}
		else{
			return function(s.charAt(0)+function(s.substring(1,s.length())));
		}
	}
    
	static boolean isPowerOfTwo(int n){
    	if(n==0)
    		return false;
 
		return (int)(Math.ceil((Math.log(n) / Math.log(2)))) == 
       			(int)(Math.floor(((Math.log(n) / Math.log(2)))));
	}

	static boolean isPerfectSquare(double x)
    {
        if (x >= 0) {
            double sr = Math.sqrt(x);
            return ((sr * sr) == x);
        }
        return false;
    }

	public static boolean isPerfect(int n){
		int a = (int)Math.sqrt(n);
		if(a*a==n){
			return true;
		}
		return false;
	}

	public static boolean check(String s){
		if(s.length()==1){
			return true;
		}
		for(int i=1;i<s.length();i++){
			if(s.charAt(i)==s.charAt(i-1)){
				return false;
			}
		}
		return true;
	}

	public static boolean isPrime(int n){
		boolean flag=true;
		while(n%2==0){
			n=n/2;
			flag=false;
		}
		for(int i=3;i<=Math.sqrt(n);i+=2){
			if(n%i==0){
				flag=false;
				while(n%i==0){
					n=n/i;
				}
			}
		}
		return flag;
	}

	public static void dfst(ArrayList<ArrayList<Integer>> graph,int src, int deg,boolean ef, boolean of, boolean[] vis, boolean[] flip, int[] init, int[] goal){
		if(vis[src]){
			return;
		}
		vis[src]=true;
		if((deg%2==0 && ef) || (deg%2==1 && of)){
			init[src]=1-init[src];
		}
		if(init[src]!=goal[src]){
			flip[src]=true;
			if(deg%2==0){
				ef=!ef;
			}
			else{
				of=!of;
			}
		}
		for(int i=0;i<graph.get(src).size();i++){
			if(!vis[graph.get(src).get(i)]){
				dfst(graph,graph.get(src).get(i),deg+1,ef,of,vis,flip,init,goal);
			}
		}
	}

	public static void dfs(ArrayList<ArrayList<Integer>> graph, int src, int val, boolean[] vis){
		vis[src]=true;
		int cur_val =0;
		for(int i=0;i<graph.get(src).size();i++){
			if(!vis[graph.get(src).get(i)]){
				cur_val=val+1;
				dfs(graph,graph.get(src).get(i),cur_val,vis);
			}
			if(max_value<cur_val){
				max_value=cur_val;
			}
			cur_val=0;
		}
	}

	public static ArrayList<Integer> pf(int n){
		ArrayList<Integer> arr = new ArrayList<>();
		boolean flag=false;
		while(n%2==0){
			flag=true;
			n/=2;
		}
		if(flag){
			arr.add(2);
		}
		for(int i=3;i<=Math.sqrt(n);i++){
			if(n%i==0){
				arr.add(i);
				while(n%i==0){
					n/=i;
				}
			}
		}
		if(n>1){
			arr.add(n);
		}
		return arr;
	}

	static int gcd(int a, int b){
		if(b==0){
			return a;
		}
		else{
			return gcd(b,a%b);
		}
	}

	static boolean function(int n, int i, int[] arr, int sum){
		if(sum==0){
			return true;
		}
		if(i==n && sum!=0){
			return false;
		}
		if(sum<arr[i]){
			return function(n,i+1,arr,sum);
		}
		else{
			return function(n,i+1,arr,sum-arr[i]) || function(n,i+1,arr,sum);
		}
	}

	public static long fact( long n, long mod){
		long res =1;
		for(int i=1;i<=n;i++){
			res%=mod;
			i%=mod;
			res=(res*i)%mod;
		}
		return res;
	}

	public static long nCk(long n,long k, long mod){
		return (fact(n,mod)%mod*modular(fact(k,mod),mod-2,mod)%mod*modular(fact(n-k,mod),mod-2,mod)%mod)%mod;
	}

	public static long modular(long n, long e, long mod){
		long res = 1;
		n%=mod;
		if (n == 0) return 0;
		while(e>0){
			if((e&1)==1){
				res=(res*n)%mod;
			}
			e=e>>1;
			n=(n*n)%mod;
		}
		return res;
	}

	static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
 
        String next() {
            while (!st.hasMoreTokens())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }
        long[] readLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        long[][] twoDArray(int n, int m){
        	long[][] arr = new long[n][m];
        	for(int i=0;i<n;i++){
        		for(int j=0;j<m;j++){
        			arr[i][j]=nextLong();
        		}
        	}
        	return arr;
        }
    }
}

class Point implements Comparable<Point>{
	long start;
	long end;
	long val;
	Point(long start, long end, long val){
		this.start=start;
		this.end=end;
		this.val=val;
	}
	// int getKey(){
	// 	return key;
	// }
	// long getValue(){
	// 	return value;
	// }
	// int getK(){
	// 	return k;
	// }
	@Override
	public int compareTo(Point p){
		if(this.end-p.end>0){
			return 1;
		}
		else if(this.end==p.end){
			return 0;
		}
		else{
			return -1;
		}
	}
}
class Node{
	int idx;
	int val;
	Node(int a,int b){
		idx=a;
		val=b;
	}
}