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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;


public class C{
	
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }
	
	static class Pair
    {
		int x;
		int y;
		
		Pair(int x,int y)
		{
			this.x = x;
			this.y = y;
		}
    }
	
/*
	static class SegmentTree {
        public int[] seg;
        public int N;
        public int size;

        public SegmentTree(int n) {
            
        	int h = (int)Math.ceil((double)Math.log(n)/Math.log(2));
        	
        	this.size = (int)Math.pow(2,h)*2-1;
        	seg = new int[size];
        }



        public int update(int l, int r, int i, int val) {
        	
        	
        	if(l == r && l == val)
        	{
        		seg[i]++;
        		return seg[i];
        	}
        	if(l > r || l == r || val > r || val < l) return seg[i];
            int m = (l+r) >>> 1;
            
            int left = update(l,m,2*i+1,val);
            
            int right = update(m+1,r,2*i+2,val);
            
            seg[i] = left+right;
            return seg[i];
        }

        

        public int getValue(int l, int r, int i, int ql, int qr) {
        	
            if (l > r || ql > qr || l > qr || r < ql) return 0;
            if (l == r) {
                return seg[i];
            }
            if (l >= ql && r <= qr) {
                return seg[i];
            }
            int m = (l + r) >>> 1;
            return getValue(l, m, 2 * i + 1, ql, qr) + getValue(m + 1, r, 2 * i + 2, ql, qr);
        }

    }
	
	public static int gcd(int a,int b)
	{
		if(a == 0) return b;
		if(b == 0) return a;
		
		return gcd(b, a%b);
	}
*/
	
	public static long rec(int l,int r,int n)
	{	
		if(l > r) return 0;
		if(l == r) return m[l];
		
		int mini = queryST(l,r);
		if(mini < l || mini > r)
		{
			throw new ArithmeticException("Out of range");
		}
		int minv = m[mini];
		
		long sum = (long)(mini-l+1)*(long)minv;
		
		sum += rec(mini+1,r,n);
		
		long ans = sum;
		
		sum = (long)(r-mini+1)*(long)minv;
		
		sum += rec(l,mini-1,n);

		//System.out.println("Added "+l+" "+r);
		if(ans > sum)
		{		
			hm.put((long)l*n + (long)r,0);
			return ans;
		}
		else
		{	
			hm.put((long)l*n + (long)r,1);
			return sum;
		}
	}

	static int m[],logN[];
	static int st[][];
	static HashMap<Long,Integer> hm = new HashMap<>();

	
	static void makeST(int n) 
	{
	    logN[1] = 0;
	    for (int i = 2; i <= n; i++)
	        logN[i] = logN[i/2] + 1;
	    for (int i = 1; i <= n; i++) 
	        st[i][0] = i;
	    for (int j = 1; j < 30; j++) {
	        for (int i = 1; i <= n; i++) {
	            st[i][j] = st[i][j-1];
	            if (i+(1<<(j-1)) <= n && m[st[i+(1<<(j-1))][j-1]] < m[st[i][j]])
	                st[i][j] = st[i+(1<<(j-1))][j-1];
	        }
	    }
	}
	 
	static int queryST(int s, int e) {
	    int len = e - s + 1;
	    int l = logN[len];
	    int res = st[s][l];
	    if (m[st[e-(1<<l)+1][l]] < m[res]) res = st[e-(1<<l)+1][l];
	    return res;
	}
	
	public static void main(String[] args) 
	{
		OutputStream outputStream = System.out;
        FastReader sc = new FastReader();
        PrintWriter out = new PrintWriter(outputStream);
        
        int t = sc.nextInt();
        
        while(t-- > 0)
        {
        	int n = sc.nextInt();
        	
        	int b[] = new int[n];
        	int map[] = new int[2*n+1];
        	HashSet<Integer> hs = new HashSet<>();
        	for(int i = 0; i < n; i++)
        	{
        		b[i] = sc.nextInt();
        		map[b[i]] = i;
        		hs.add(b[i]);
        	}
        	
        	
        	
        	int a[] = new int[2*n];
        	
        	Arrays.fill(a,0);
        	
        	boolean pos = true;
        	for(int i = 0; i < n; i++)
        	{	
        		int v = b[i];
        		a[2*i] = v;
        		for(int j = v+1; j <= 2*n; j++)
        		{
        			if(!hs.contains(j))
        			{
        				a[2*i+1] = j;
        				hs.add(j);
        				break;
        			}
        		}
        		if(a[2*i+1] == 0)
        		{
        			pos = false;
        			break;
        		}
        	}
        	
        	if(!pos) out.println(-1);
        	
        	else
        	{
        		for(int i = 0; i < 2*n; i++)
        		{
        			out.print(a[i]+" ");
        		}
        		out.println();
        	}
        }
        out.close();
	}

}