Problem: You are given a sequence b_1, b_2, …, b_n. Find the lexicographically minimal permutation a_1, a_2, …, a_{2n} such that b_i = min(a_{2i-1}, a_{2i}), or determine that it is impossible.

Input

Each test contains one or more test cases. The first line contains the number of test cases t (1 ≤ t ≤ 100).

The first line of each test case consists of one integer n — the number of elements in the sequence b (1 ≤ n ≤ 100).

The second line of each test case consists of n different integers b_1, …, b_n — elements of the sequence b (1 ≤ b_i ≤ 2n).

It is guaranteed that the sum of n by all test cases doesn't exceed 100.

Output

For each test case, if there is no appropriate permutation, print one number -1.

Otherwise, print 2n integers a_1, …, a_{2n} — required lexicographically minimal permutation of numbers from 1 to 2n.

Example

Input


5
1
1
2
4 1
3
4 1 3
4
2 3 4 5
5
1 5 7 2 8


Output


1 2 
-1
4 5 1 2 3 6 
-1
1 3 5 6 7 9 2 4 8 10 

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
public class Solution{
  
    static long mod=998244353 ;
    static boolean f=true;
    static class pair implements Comparable<pair>{
        int a,b,c;
        pair(int x,int y,int z){
            a=x;b=y;c=z;
        }
        public int compareTo(pair t){
           if(c<t.c)    return 1;
		    else if(c==t.c)
		    {   if(a<t.a)    return -1;
		        else if(a>t.a)   return 1;
		        else    return 0;
		    }
		    else    return -1;
        }
    }
    // public static ArrayList<pair> bfs(String[] a,int r,int c){
    //     ArrayList<pair> ans=new ArrayList<>();
    //     Queue<pair> q=new LinkedList<>();
    //     int[][] dxy={{-1,0,1,0},{0,-1,0,1}};
    //     q.add(new pair(r,c));
    //     HashSet<String> h=new HashSet<>();
    //     while(!q.isEmpty()){
    //         pair f=q.poll();
    //         ans.add(f);h.add(f.a+" "+f.b);
    //         for(int i=0;i<4;i++){
    //             int dx=f.a+dxy[0][i];
    //             int dy=f.b+dxy[1][i];
    //             if(dx<0||dy<0||dx>=a.length||dy>=a.length||h.contains(dx+" "+dy)||
    //             a[dx].charAt(dy)=='1')
    //             continue;
    //             q.add(new pair(dx,dy));
    //             h.add(dx+" "+dy);
    //         }
    //     }
    //     return ans;
    // }    

    /*
    1 1 1 1 1 
3 3 3 
2 3 3 2 1 3 
1 
2 2 2 2 
4 4 4 1 4 
*/
    public static int pow(int a, int n) {
		long ans = 1;
		long base = a;
		while (n != 0) {
			if ((n & 1) == 1) {
				ans *= base;
				ans %= 1000000007;
			}
			base = (base * base) % 1000000007;
			n >>= 1;
		}
		return (int) ans % 1000000007;
	}
	public static int find(int x){
	    int i=1;int f=0;
	    while(x>0){
	        if((x&1)==0)f=i;
	        x>>=1;i++;
	    }
	    return f;
	}
	public static boolean good(int x){
	    
	    if((((x+1)&x))==0)
	    return true;
	    return false;
	}
	public static long f(long n){
	  
	   long val=2;
	   long preval=0;int i=1;
	   while(n>=val){
	       i++;
	       preval=val;
	       val=3*i+val-1;
	       
	   }
	   
	   return preval;
	   
	}
	public static boolean bfs(ArrayList<Integer>[] a,int n,int[] b){
	    Queue<Integer> p=new LinkedList<>();
	    boolean v[]=new boolean[n];
	    v[0]=true;int k=0;
	    if(b[0]!=0)return false;
	    p.add(0);int c=1;
	    HashSet<Integer> h=new HashSet<Integer>();
	    h.add(0);
	    while(!p.isEmpty()){
	        int f=p.poll();k++;
	        if(h.contains(f))h.remove(f);
	        else return false;
	        v[f]=true;
	        c--;
	
	       for(int i:a[f]){
	           if(!v[i]){
	           p.add(i);v[i]=true;}
	       }
	          if(c==0){
	              c=p.size();
	       if(h.size()!=0)return false;
	       for(int j=k;j<k+p.size();j++)
	       h.add(b[j]);
	   }
	    }
	    return true;
	    
	}
	public static int mi(int[] a,int k,int[] dp,int n){
	    int max=0;
	    for(int i=1;i*i<=k;i++){
	      //  System.out.println("fact "+i);
	        if(k%i==0&&(a[i-1]<a[k-1])){
	            
	      //  System.out.println(i+" "+dp[i-1]+" "+a[i-1]+" ");
	        max=Math.max(dp[i-1],max);}
	        if(k%i==0&&(a[k/i-1]<a[k-1])){
	            
	      //  System.out.println(i+" "+dp[i-1]+" "+a[i-1]+" ");
	        max=Math.max(dp[k/i-1],max);}
	        
	    }
	    return max;
	}
	    public static long dfs(ArrayList<Integer> a[],int n,boolean[] v,boolean s[]
	    ,long c[],int x){
     v[n]=true;
     if(n==x)
     s[n]=true;
     c[n]=1;
      
        for(int i=0;i<a[n].size();i++){
            if(!v[a[n].get(i)]){
         c[n]+= dfs(a,a[n].get(i),v,s,c,x);
         s[n]|=s[a[n].get(i)];
            }
           
        }
        return c[n];
        
    }
    public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
 
			int t = s.nextInt();
	StringBuilder st=new StringBuilder();
		while(t-- > 0) {
int n=s.nextInt();
HashSet<Integer> h=new HashSet<>();
int[]a=new int[n];
for(int i=0;i<n;i++){
    a[i]=s.nextInt();
    h.add(a[i]);
}
StringBuilder ans=new StringBuilder();
boolean f=true;
for(int i=0;i<n;i++){
    int k=1;
    while(a[i]+k<=2*n&&h.contains(a[i]+k))k++;
    if(a[i]+k>2*n){
        f=false;break;
    }
    h.add(a[i]+k);
  ans.append(a[i]+" "+(a[i]+k)+" ");
}
 if(!f)
 st.append("-1\n");
 else
st.append(ans+"\n");
}
System.out.println(st);
   
/*

2
1
3
1
6


6 23 21
1 1000 0
2 1 2

0
40
41664916690999888

1 
1 2 
2 1 3 
3 1 2 4 
2 4 1 3 5 
3 4 1 5 2 6 


6 45 46
2 2 1
3 4 2
4 4 3
*/


  
	
        
    }
}