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.*;
import java.io.*;
import java.util.*;
import java.util.List;

public class Main {

    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;

        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(
                    new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    } else {
                        continue;
                    }
                }
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0,
                    BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }
//
//

    //    static class TreeNode {
//        int val;
//        TreeNode left,right;
//        TreeNode(int val){
//            this.val=val;left=null;right=null;
//        }
//    }
//    static TreeNode maxx(int start,int end,int[] arr){
//        if(start>end){
//            return null;
//        }
//        int ind=0;
//        int max=-1;
//        for(int j=start;j<=end;j++){
//            if(arr[j]>max){
//                max=arr[j];
//                ind=j;
//            }
//        }
//        TreeNode jj=new TreeNode(arr[ind]);
//        jj.left=maxx(start,ind-1,arr);
//        jj.right=maxx(ind+1,end,arr);
//        return jj;
//
//    }
//    static void dfs(TreeNode root,int dep){
//        if(root==null){
//            return;
//        }
//        ans[hashMap.get(root.val)]=dep;
//        dfs(root.left,dep+1);
//        dfs(root.right,dep+1);
//    }
//    static int[] ans;
//   static HashMap<Integer,Integer> hashMap;
//   static class pont{
//       int val,index;
//       pont(int val,int index){
//           this.val=val;
//           this.index=index;
//       }
//   }
//   static class compr implements Comparator<pont>{
//       public int compare(pont a,pont b){
//           return a.val-b.val;
//       }
//   }
//    static class poin{
//       int src;
//       long val;
//       poin(int src,long val){
//           this.src=src;
//           this.val=val;
//       }
//    }
//
//    static double maxx(int flag,String s,String t,int k){
//
//       if(flag==0){
//
//           StringBuilder stringBuilder = new StringBuilder(s.substring(0,s.length()-1));
//           double ans= 0.0;
//           for(int j=1;j<10;j++){
//               StringBuilder str=new StringBuilder(stringBuilder);
//               str.append(j);
//
//               ans=(double)((double)ans+(double)maxx(1,str.toString(),t,k));
//           }
//           return ans;
//       }
//       else if(flag==1){
//
//           StringBuilder stringBuilder = new StringBuilder(t.substring(0,t.length()-1));
//           double ans= 0.0;
//           for(int j=1;j<10;j++){
//               StringBuilder str=new StringBuilder(stringBuilder);
//               str.append(j);
//               ans=(double)((double)ans+(double)maxx(2,s,str.toString(),k));
//           }
//           return ans;
//
//       }
//       else{
//           long[] count=new long[10];
//           long taka=0;
//           long[] tot=new long[10];
//
//           for(int j=0;j<s.length();j++){
//               int a=Integer.parseInt(String.valueOf(s.charAt(j)));
//               count[a]++;
//               tot[a]++;
//           }
//           for(int j=1;j<10;j++){
//               taka=(long)((long)taka+(long)((long)Math.pow(10,count[j])*(long)j));
//           }
//           long aoki=0;
//           count=new long[10];
//           for(int j=0;j<t.length();j++){
//               int a=Integer.parseInt(String.valueOf(t.charAt(j)));
//               count[a]++;
//               tot[a]++;
//           }
//           for(int j=1;j<10;j++){
//               aoki=(long)((long)aoki+(long)((long)Math.pow(10,count[j])*(long)j));
//           }
//           if(aoki>=taka){
//               return 0;
//           }else{
//               if(t.charAt(t.length()-1)==s.charAt(s.length()-1)){
//                   double kk=(double)k-(double)tot[Integer.parseInt(String.valueOf(t.charAt(t.length()-1)))]+(double)2;
//                   return (double)((double)((double)(kk)*(double)(kk-(double)1))/(double)((double)1*((double)9*(double)k-(double)8)*(double)((double)9*(double)k-(double)9)));
//
//               }else{
//                   double kk=(double)k-(double)tot[Integer.parseInt(String.valueOf(t.charAt(t.length()-1)))]+(double)1;
//                   double kk2=(double)k-(double)tot[Integer.parseInt(String.valueOf(s.charAt(s.length()-1)))]+(double)1;
//                   return (double)(((double)((double)1*(double)kk)*(double)(kk2))/(double)((double)1*((double)9*(double)k-(double)8)*(double) ((double)9*(double)k-(double)9)));
//               }
//           }
//
//       }
//
//
//    }
//
//   static void sieveOfEratosthenes(int n)
//    {
//        boolean prime[] = new boolean[n + 1];
//        for (int i = 0; i <= n; i++)
//            prime[i] = true;
//
//        for (int p = 2; p * p <= n; p++)
//        {
//            if (prime[p] == true)
//            {
//                for (int i = p * p; i <= n; i += p)
//                    prime[i] = false;
//            }
//        }
//
//        for (int i = 2; i <= n; i++)
//        {
//            if (prime[i] == true)
//                treeMap.put(i,0);
//        }
//    }
//    static TreeMap<Integer,Integer> treeMap;
    static class comp implements Comparator<Point> {
        public int compare(Point a, Point b) {
            if (b.y == a.y) {
                return a.x - b.x;
            }
            return b.y - a.y;
        }
    }

    static boolean ff = false;

    //    static void maxx(int ind,int l,int r,int d,int u,int n)
//    {
//        if(ind==4){
//            if(l<0 || r<0 || u<0 || d<0){
//                return;
//            }
//            ff=true;
//            return;
//        }
//        if(ind==0){
//            if(l==n){
//                maxx(ind+1,l-2,r,d-1,u-1,n);
//            }else if(l==n-1){
//                maxx(ind+1,l-1,r,d-1,u,n);
//                if(ff){
//                    return;
//                }
//                maxx(ind+1,l-1,r,d,u-1,n);
//            }else{
//                maxx(ind+1,l,r,d,u,n);
//            }
//
//        }else if(ind==1){
//            if(r==n){
//                maxx(ind+1,l,r-2,d-1,u-1,n);
//            }else if(r==n-1){
//                maxx(ind+1,l,r-1,d-1,u,n);
//                if(ff){
//                    return;
//                }
//                maxx(ind+1,l,r-1,d,u-1,n);
//            }else{
//                maxx(ind+1,l,r,d,u,n);
//            }
//
//        }else if(ind==2){
//            if(d==n){
//                maxx(ind+1,l-1,r-1,d-2,u,n);
//            }else if(d==n-1){
//                maxx(ind+1,l-1,r,d-1,u,n);
//                if(ff){
//                    return;
//                }
//                maxx(ind+1,l,r-1,d-1,u,n);
//            }else{
//                maxx(ind+1,l,r,d,u,n);
//            }
//
//        }else{
//            if(u==n){
//                maxx(ind+1,l-1,r-1,d,u-2,n);
//            }else if(u==n-1){
//                maxx(ind+1,l-1,r,d,u-1,n);
//                if(ff){
//                    return;
//                }
//                maxx(ind+1,l,r-1,d,u-1,n);
//            }else{
//                maxx(ind+1,l,r,d,u,n);
//            }
//        }
//    }
//    static void filereader() throws IOException{
//        FileReader fileReader=new FileReader("input.txt");
//        int ch;
//        String str="";
//        StringBuilder stringBuilder=new StringBuilder();
//        while ((ch=fileReader.read())!=-1)
//            stringBuilder.append((char)ch);
//
//        fileReader.close();
//        StringBuilder ans=new StringBuilder();
//        FileWriter fw=new FileWriter("output.txt");
//        for(int j=0;j<ans.length();j++){
//            fw.write(ans.charAt(j));
//        }
//        fw.close();
//    }
    static class point {
        int w, v;

        point(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    static class compp implements Comparator<point> {
        public int compare(point a, point b) {
            return b.v - a.v;
        }
    }

    //    static int cal(int ind,String s,String x,int val){
//        if(ind>=s.length()){
//            if(val%7==0){
//                return 1;
//            }else{
//                return 0;
//            }
//        }
//        if(aa[ind][val]!=-1){
//            return aa[ind][val];
//        }
//
//        if(x.charAt(ind)=='A'){
//            int ii=Integer.parseInt(String.valueOf(s.charAt(ind)));
//            return aa[ind][val]=Math.min( cal(ind+1,s,x,(val*10)%7  ),cal(ind+1,s,x, (val*10+ii)%7 )  );
//        }else{
//            int ii=Integer.parseInt(String.valueOf(s.charAt(ind)));
//            return aa[ind][val]=Math.max( cal(ind+1,s,x,(val*10)%7  ),cal(ind+1,s,x, (val*10+ii)%7 )  );
//        }
//
//    }
//    static int aa[][];
    static List<Integer> findprime(int n) {
        List<Integer> primes = new ArrayList<>();
        boolean[] prime = new boolean[n];
        for (int j = 1; j < prime.length; j++) {
            prime[j] = true;
        }
        for (int j = 2; j * j < prime.length; j++) {
            if (!prime[j]) {
                continue;
            }
            for (int i = j * j; i < prime.length; i = i + j) {
                prime[i] = false;
            }
        }
        for (int j = 2; j < prime.length; j++) {
            if (prime[j]) {
                primes.add(j);
            }
        }
        return primes;
    }

    //    static long calculateWays(int ind,int bit,int[] primes,long a,long b,int[] flags){
//
//        long num=(long)((long)ind+(long)a);
//        if(num>b){
//            return 1;
//        }
//        if(aaa[ind][bit]!=-1){
//            return aaa[ind][bit];
//        }
//
//        long tot=0;
////        int flag=0;
////        int bitt=bit;
////        for(int j=0;j<primes.length;j++){
////            int jj= (int)bit & (int)Math.pow(2,j);
////
////            if(jj!=0 && num%(long)primes[j]==0 ){
////                flag=1;
////                break;
////            }
////            if( num%(long)primes[j]==0 ){
////                bitt=(int)bitt | (int)Math.pow(2,j);
////
////            }
////        }
//        int jj=(int)(flags[ind] & (int)bit);
//        if( jj==0){
//            tot=(long)((long)tot+(long)calculateWays(ind+1,bit | flags[ind],primes,a,b,flags));
//            tot=(long)((long)tot+(long)calculateWays(ind+1,bit,primes,a,b,flags));
//
//        }else{
//            tot=(long)((long)tot+(long)calculateWays(ind+1,bit,primes,a,b,flags));
//        }
//
//        return aaa[ind][bit]=tot;
//    }
    static long[][] aaa;

    static long maxx(String str, int n, long val) {

        if (hashMap.get(str) != null) {
            return hashMap.get(str);
        }
        long tot = 0;
        if (str.equals("")) {
            for (int j = 1; j <= 9; j++) {
                tot = tot + maxx(str + String.valueOf(j), n, val);
            }
            hashMap.put(str, tot);

            return tot;
        } else {
            String ss = str + str;
            if (Long.parseLong(ss) > val) {
                return 0;
            }
            if (str.length() == n) {
                return 1;
            }
            for (int j = 0; j <= 9; j++) {
                tot = tot + maxx(str + String.valueOf(j), n, val);
            }
            hashMap.put(str, tot);
            return tot;
        }

    }

    static class poi {
        int freq, occur, num;

        poi(int freq, int occur, int num) {
            this.freq = freq;
            this.num = num;
            this.occur = occur;
        }
    }

    static class poii {
        int day, tot;

        poii(int day, int tot) {
            this.day = day;
            this.tot = tot;
        }
    }

    static class comp2 implements Comparator<poii> {
        public int compare(poii a, poii b) {
            return a.tot - b.tot;
        }
    }

    static class comp1 implements Comparator<poi> {
        @Override
        public int compare(poi o1, poi o2) {
            if (o2.occur == o1.occur) {
                return o1.freq - o2.freq;
            }
            return o1.occur - o2.occur;
        }
    }

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

    static HashMap<String, Long> hashMap;

    static class poit {
        int freq, val;

        poit(int freq, int val) {
            this.freq = freq;
            this.val = val;
        }
    }

    static class com implements Comparator<poit> {
        public int compare(poit a, poit b) {
            return b.freq - a.freq;
        }
    }

    public static void main(String[] args) throws IOException {

        Reader s = new Reader();
        int t = s.nextInt();
        for (int j = 0; j < t; j++) {
            int n = s.nextInt();
            int[] arr=new int[n];
            TreeMap<Integer,Integer> treeMap=new TreeMap<>();
            TreeMap<Integer,Integer> treeMap1=new TreeMap<>();

            for(int i=0;i<n;i++){
                arr[i]=s.nextInt();
                treeMap.put(i+1,0);
                treeMap1.put(i+1,0);
            }
            int[] ans=new int[n];
            int[] ans1=new int[n];

            ans[0]=arr[0];
            HashSet<Integer> has=new HashSet<>();
            int k=1;
            StringBuilder stringBuilder=new StringBuilder();
            StringBuilder stringBuilder1=new StringBuilder();
            treeMap.remove(ans[0]);
//            has.add(ans[0]);
            stringBuilder.append(ans[0]);
            stringBuilder.append(" ");
            for(int i=1;i<n;i++){
                if(arr[i]!=arr[i-1]){
                    ans[i]=arr[i];
                    treeMap.remove(ans[i]);
                    has.add(ans[i]);
                }else{
//                    while(has.contains(k)){
//                        k++;
//                    }
                    int tt=treeMap.ceilingKey(k);
//                    has.add(k);
                    ans[i]=tt;
                    k=tt+1;
                    treeMap.remove(tt);
                }
                stringBuilder.append(ans[i]);
                stringBuilder.append(" ");

            }

            ans1[0]=arr[0];
            has=new HashSet<>();
            stringBuilder1.append(ans1[0]);
            stringBuilder1.append(" ");
            k=ans1[0]-1;
            treeMap1.remove(ans1[0]);
            has.add(ans1[0]);
            for(int i=1;i<n;i++){
                if(arr[i]!=arr[i-1]){
                    ans1[i]=arr[i];
                    treeMap1.remove(ans1[i]);
//                    has.add(ans1[i]);
                    k=ans1[i]-1;
                }else{
//                    while(has.contains(k)){
//                        k--;
//                    }
                    int tt=treeMap1.floorKey(k);
//                    has.add(k);
                    ans1[i]=tt;
                    treeMap1.remove(tt);
                    k=tt-1;
                }
                stringBuilder1.append(ans1[i]);
                stringBuilder1.append(" ");

            }
            System.out.println(stringBuilder.toString().trim());
            System.out.println(stringBuilder1.toString().trim());

        }


//        BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
//        int t = Integer.parseInt(s.readLine().trim());
//        for (int j = 0; j < t; j++) {
//             String str=s.readLine().trim();
//            HashSet<Character> hashSet=new HashSet<>();
//            int[] arr=new int[26];
//            int[] aar=new int[26];
//            int[] last=new int[26];
//
//            List<Character> list=new ArrayList<>();
//
//            for(int i=0;i<str.length();i++){
//                 if(hashSet.contains(str.charAt(i))){
//                     if(aar[str.charAt(i)-'a']==0){
////                        list.add(str.charAt(i));
//                        aar[str.charAt(i)-'a']=1;
//                     }
//                 }else{
//                     list.add(str.charAt(i));
//                 }
//                 hashSet.add(str.charAt(i));
//                 last[str.charAt(i)-'a']=i;
//             }
//             Collections.sort(list);
//             for(int i=0;i<list.size();i++){
//                 arr[list.get(i)-'a']=list.size()-1-i;
//             }
//             int priority=0;
//             StringBuilder stringBuilder=new StringBuilder();
//             for(int i=0;i<str.length();i++){
//                 if(aar[str.charAt(i)-'a']==0){
//                     stringBuilder.append(str.charAt(i));
//                     priority=arr[str.charAt(i)-'a']+1;
//                     continue;
//                 }
//                 if(priority==arr[str.charAt(i)-'a']){
//                     stringBuilder.append(str.charAt(i));
//                     priority=arr[str.charAt(i)-'a']+1;
//
//                 }else if(last[str.charAt(i)-'a']==i){
//                     stringBuilder.append(str.charAt(i));
////                     priority=arr[str.charAt(i)-'a']+1;
//
//
//
//                 }
//             }
//            System.out.println(stringBuilder.toString());


        //}






    }
}