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.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;


public class N710 {
	static PrintWriter out;
	static Scanner sc;
	static ArrayList<Integer>q,w;
	static ArrayList<Integer>adj[];
	static HashSet<Integer>primesH;
	static boolean prime[];
	//static ArrayList<Integer>a;
	static HashSet<Long>tmp;
	static boolean[]v;
	static int[]c,d;
	static int[][]dp;
	static char[][]mp;
	static int A,B,n,m,h,ans;
	static String a,b;
	public static void main(String[]args) throws IOException {
		sc=new Scanner(System.in);
		out=new PrintWriter(System.out);
		//A();
		//B();
	   // C();
	//	D();
	E();
		//F();
		out.close();
	}
	  private static void A() throws IOException {
		  int t=ni();
			while(t-->0) {
				long n=nl(),m=nl();
				long x=nl();
				long r=x%n;
				if(r==0)r=n;
				long c=(long)Math.ceil(x/(double)n);
				out.println((r-1)*m+c);
			}
		
	   }
		static void B() throws IOException {
			int t=ni();
			while(t-->0) {
				int n=ni(),k=ni();
				char[]c=ns().toCharArray();
				int a=-1,b=-1;
				for(int i=0;i<n;i++) {
					if(c[i]=='*') {
						a=i;
						c[i]='x';break;
					}
				}
				for(int i=n-1;i>=0;i--) {
					if(c[i]=='*') {
						b=i;
						c[i]='x';break;
					}
				}
				if(b==-1) {
					out.println(1);
				}else {
					int cnt=2;
					for(int i=a+k;i<b;i+=k) {
						int prev=i-k;
						while(i>prev&&c[i]!='*') {
							i--;
						}
						c[i]='x';
						cnt++;
					}
					out.println(cnt);
				}
				
			}
		}
		
		static void C() throws IOException{
			 int t=ni();
			 while(t-->0) {
				 a=ns();
				 b=ns();
				 
				 n=a.length();
				 m=b.length();
				 dp=new int[n][m];
				
				 for(int i=0;i<n;i++)Arrays.fill(dp[i], -1);
				 ans=0;
				 int lng=LCSubStr(a, b, n, m);
				 out.println(n+m-2*lng);
			 }
		}
	


		  static int LCSubStr(String s,String t,
                  int n,int m)
{ 
 
  // Create DP table
  int dp[][]=new int[2][m+1];
  int res=0;

  for(int i=1;i<=n;i++)
  {
      for(int j=1;j<=m;j++)
      {
          if(s.charAt(i-1)==t.charAt(j-1))
          {
              dp[i%2][j]=dp[(i-1)%2][j-1]+1;
              if(dp[i%2][j]>res)
                  res=dp[i%2][j];
          }
          else dp[i%2][j]=0;
      }
  }
  return res;
}
	private static int dp(int i,int j) {
			if(i<0||j<0)return 0;
			if(dp[i][j]!=-1)return dp[i][j];
			dp(i-1,j);
			dp(i,j-1);
			if(a.charAt(i)==b.charAt(j)) {
				dp[i][j]=dp(i-1,j-1)+1;
				ans=Math.max(ans,dp[i][j]);	
				return dp[i][j];
			}
			return dp[i][j]=0;
			
		}
	static void D() throws IOException {
		int t=ni();
		while(t-->0) {
			int n=ni();
			Integer[]a=new Integer[n];
			for(int i=0;i<n;i++) {
				a[i]=ni();
			}
			TreeMap<Integer, Integer>tr=new TreeMap<Integer, Integer>();
			for(int i=0;i<n;i++) {
				tr.put(a[i], tr.getOrDefault(a[i], 0)+1);
			}
			Set<Integer>k=tr.keySet();
			//Integer max=0;
			PriorityQueue<Integer>pq=new PriorityQueue<Integer>(Collections.reverseOrder());
			for(Integer x:k) {
				int v=tr.get(x);
				pq.add(v);
			}
			while(pq.size()>1) {
				int x=pq.poll()-1;
				int y=pq.poll()-1;
				if(x>0)pq.add(x);
				if(y>0)pq.add(y);
			}
			out.println(pq.isEmpty()?0:pq.peek());
		}
		
	}
	static void E() throws IOException {
		int t=ni();
		while(t-->0) {
			int n=ni();
			int[]a=nai(n);
			int[]ot1=new int[n],ot2=new int[n];
			PriorityQueue<Integer>pq1=new PriorityQueue<Integer>();
			PriorityQueue<Integer>pq2=new PriorityQueue<Integer>(Collections.reverseOrder());
			ot1[0]=ot2[0]=a[0];
			for(int i=1;i<a[0];i++) {
				pq1.add(i);
				pq2.add(i);
			}
			for(int i=1;i<n;i++) {
				if(a[i]!=a[i-1]) {
					ot1[i]=a[i];
					for(int j=a[i-1]+1;j<a[i];j++) {
						pq1.add(j);
					}
				}else {
					ot1[i]=pq1.poll();
				}
					
			}
			for(int i=1;i<n;i++) {
				if(a[i]!=a[i-1]) {
					ot2[i]=a[i];
					for(int j=a[i-1]+1;j<a[i];j++) {
						pq2.add(j);
					}
				}else {
					ot2[i]=pq2.poll();
				}
					
			}
			for(int i=0;i<n;i++) {
				out.print(ot1[i]+" ");
			}
			out.println();
			for(int i=0;i<n;i++) {
				out.print(ot2[i]+" ");
			}
			out.println();
		
		}
	}
	static int ni() throws IOException {
		return sc.nextInt();
	}
	static double nd() throws IOException {
		return sc.nextDouble();
	}
	static long nl() throws IOException {
		return  sc.nextLong();
	}
	static String ns() throws IOException {
		return sc.next();
	}
	static int[] nai(int n) throws IOException {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();
		return a;
	}
	static long[] nal(int n) throws IOException {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = sc.nextLong();
		return a;
	}
	static int[][] nmi(int n,int m) throws IOException{
		int[][]a=new int[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextInt();
			}
		}
		return a;
	}

	static long[][] nml(int n,int m) throws IOException{
		long[][]a=new long[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j]=sc.nextLong();
			}
		}
		return a;
	}
	static void o(String x) {
		out.print(x);
	}
	static void ol(String x) {
		out.println(x);
	}
	static void ol(int x) {
		out.println(x);
	}
	static void disp1(int []a) {
		for(int i=0;i<a.length;i++) {
			out.print(a[i]+" ");
		}
		out.println();
	}

	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public boolean hasNext() {return st.hasMoreTokens();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public double nextDouble() throws IOException {return Double.parseDouble(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}

		public String nextLine() throws IOException {return br.readLine();}
			
		public boolean ready() throws IOException {return br.ready(); }
		

	}
}