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.*; import java.math.*;
public class Main{
    //Don't have to see. start------------------------------------------
    static class InputIterator{
        ArrayList<String> inputLine = new ArrayList<>(1024);
        int index = 0; int max; String read;
        InputIterator(){
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            try{
                while((read = br.readLine()) != null){
                    inputLine.addAll(Arrays.asList(read.split(" ")));
                }
            }catch(IOException e){}
            max = inputLine.size();
        }
        boolean hasNext(){return (index < max);}
        String next(){
            if(hasNext()){
                return inputLine.get(index++);
            }else{
                throw new IndexOutOfBoundsException("There is no more input");
            }
        }
    }
    static HashMap<Integer, String> CONVSTR = new HashMap<>();
    static InputIterator ii = new InputIterator();//This class cannot be used in reactive problem.
    static PrintWriter out = new PrintWriter(System.out);
    static void flush(){out.flush();}
    static void myout(Object t){out.println(t);}
    static void myerr(Object t){System.err.print("debug:");System.err.println(t);}
    static String next(){return ii.next();}
    static boolean hasNext(){return ii.hasNext();}
    static int nextInt(){return Integer.parseInt(next());}
    static long nextLong(){return Long.parseLong(next());}
    static double nextDouble(){return Double.parseDouble(next());}
    static ArrayList<String> nextCharArray(){return myconv(next(), 0);}
    static ArrayList<String> nextStrArray(int size){
        ArrayList<String> ret = new ArrayList<>(size);
        for(int i = 0; i < size; i++){
            ret.add(next());
        }
        return ret;
    }
    static ArrayList<Integer> nextIntArray(int size){
        ArrayList<Integer> ret = new ArrayList<>(size);
        for(int i = 0; i < size; i++){
            ret.add(Integer.parseInt(next()));
        }
        return ret;
    }
    static ArrayList<Long> nextLongArray(int size){
        ArrayList<Long> ret = new ArrayList<>(size);
        for(int i = 0; i < size; i++){
            ret.add(Long.parseLong(next()));
        }
        return ret;
    }
    @SuppressWarnings("unchecked")
    static String myconv(Object list, int no){//only join
        String joinString = CONVSTR.get(no);
        if(list instanceof String[]){
            return String.join(joinString, (String[])list);
        }else if(list instanceof ArrayList){
            return String.join(joinString, (ArrayList)list);
        }else{
            throw new ClassCastException("Don't join");
        }
    }
    static ArrayList<String> myconv(String str, int no){//only split
        String splitString = CONVSTR.get(no);
        return new ArrayList<String>(Arrays.asList(str.split(splitString)));
    }
    public static void main(String[] args){
        CONVSTR.put(8, " "); CONVSTR.put(9, "\n"); CONVSTR.put(0, "");
        solve();flush();
    }
    //Don't have to see. end------------------------------------------
    static void solve(){//Here is the main function
        int t = nextInt();
        for(int i = 0; i < t; i++){
            int N = nextInt();
            TreeSet<Integer> set1 = new TreeSet<>();
            TreeSet<Integer> set2 = new TreeSet<>();
            for(int j = 1; j <= N; j++){
                set1.add(j);
                set2.add(j);
            }
            ArrayList<Integer> list = nextIntArray(N);
            String[] output1 = new String[N];
            String[] output2 = new String[N];
            for(int j = 0; j < N; j++){
                int check = list.get(j);
                if(set1.contains(check)){
                    set1.remove(check);
                    output1[j] = String.valueOf(check);
                }else{
                    int min = set1.first();
                    output1[j] = String.valueOf(min);
                    set1.remove(min);
                }
            }
            int last = -1;
            for(int j = 0; j < N; j++){
                int check = list.get(j);
                if(set2.contains(check)){
                    set2.remove(check);
                    output2[j] = String.valueOf(check);
                    last = check;
                }else{
                    int max = (int)set2.lower(last);
                    output2[j] = String.valueOf(max);
                    set2.remove(max);
                }
            }
            myout(myconv(output1, 8));
            myout(myconv(output2, 8));
        }
    }
    //Method addition frame start



    //Method addition frame end
}