You are given an array B of length 2N . You have an unknown array A which is sorted and contains *distinct* elements. You need to find out the array A. B contains all the medians of each prefix and suffix of the array A.

A median is the middle element in a sorted array . [1,2,3,4] has median 2 and [1,3,4] has 3 as median.

Determine whether B is a valid array of some array A. If yes find the array A else print -1.

------ Input Format ------ 

- The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N.
- The second line of each test case contains 2N space-separated integers B_{1}, B_{2}, \dots, B_{N}.

------ Output Format ------ 

For each testcase, output the valid array A or -1 if not possible.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$1 ≤B_{i} ≤10^{6}$
- Sum of N overall testcases won't exceed $2*10^{5}$.

------ subtasks ------ 

100 points : Original Constraints

----- Sample Input 1 ------ 
2
3
6 5 5 7 6 6
3
1 2 1 4 2 4
----- Sample Output 1 ------ 
5 6 7
-1
----- explanation 1 ------ 
- Test case $1$: Assume the array $A$ be $[5,6,7]$. The medians of the prefix arrays of $A$ are 
- $[5]$ = $5$
- $[5,6]$ = $5$
- $[5,6,7]$ = $6$

The medians of the suffix arrays of $A$ are 
- $[7]$ = $7$
- $[6,7]$ = $6$
- $[5,6,7]$ = $6$

Hence $B$ contains all the medians above with the element $5$ repeating exactly $2$ times,
$6$ repeating exactly $3$ times and $7$ repeating only once.

- Test case $2$: no valid array $A$ can be found.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	B = [int(k) for k in input().split()]
	B.sort()
	d = dict()
	for k in range(2 * n):
		if B[k] not in d:
			d[B[k]] = 1
		else:
			d[B[k]] += 1
	c = list(set(B))
	c.sort()
	if n == 1:
		if B[0] == B[1]:
			print(B[0])
		else:
			print(-1)
		continue
	for k in range(len(c)):
		if k == len(c) - 1:
			if d[c[k]] == 1:
				pass
			else:
				print(-1)
				break
		elif k == (n - 1) // 2:
			if d[c[k]] == 3:
				pass
			else:
				print(-1)
				break
		elif d[c[k]] == 2:
			pass
		else:
			print(-1)
			break
	else:
		print(*c)


for _ in range(int(input())):
	n = int(input())
	my = map(int, input().split())
	out = []
	cnt = {}
	for x in my:
		if x in cnt.keys():
			cnt[x] += 1
		else:
			cnt[x] = 1
			out.append(x)
	out.sort()
	if n == 1:
		if len(out) > 1:
			print(-1)
		else:
			print(out[0])
		continue
	if n == 2:
		if cnt[out[0]] != 3 or cnt[out[-1]] != 1:
			print(-1)
		else:
			print(out[0], end=' ')
			print(out[1])
		continue
	ans = True
	if cnt[out[-1]] != 1:
		ans = False
	if n % 2 == 0:
		if cnt[out[len(out) // 2 - 1]] != 3:
			ans = False
		for i in range(len(out) - 1):
			if cnt[out[i]] != 2 and i != len(out) // 2 - 1:
				ans = False
	else:
		if cnt[out[len(out) // 2]] != 3:
			ans = False
		for i in range(len(out) - 1):
			if cnt[out[i]] != 2 and i != len(out) // 2:
				ans = False
	if ans == True:
		for v in out:
			print(v, end=' ')
	else:
		print(-1)
	print()


for i in range(int(input())):
	N = int(input())
	B = list(map(int, input().split()))
	d1 = {}
	for i in B:
		if i in d1:
			d1[i] += 1
		else:
			d1[i] = 1
	A = []
	for i in d1:
		A.append(i)
	A.sort()
	check = 0
	for i in range(len(A)):
		if i % 2 == 0 or i == 1:
			mid = i / 2
		else:
			mid = (i + 1) / 2
			mid -= 1
		val = A[int(mid)]
		if val in d1:
			d1[val] -= 1
		else:
			check = 1
			break
	A.reverse()
	for i in range(len(A)):
		if i % 2 == 0:
			mid = i / 2
		else:
			mid = (i + 1) / 2
		if A[int(mid)] in d1:
			d1[A[int(mid)]] -= 1
		else:
			check = 1
			break
	if check == 1:
		print('-1')
	else:
		check = 0
		for i in d1:
			if d1[i] != 0:
				print('-1')
				check = 1
				break
		if check != 1:
			A.reverse()
			for i in A:
				print(str(i) + ' ', end='')
			print()


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	m = 2 * n
	s = list(set(l))
	c = []
	if len(s) != n:
		print(-1)
		continue
	l.sort()
	if n % 2 == 0:
		x = n // 2 - 1
	else:
		x = n // 2
	s.sort()
	for j in range(x):
		c.append(s[j])
		c.append(s[j])
	c.append(s[x])
	c.append(s[x])
	c.append(s[x])
	for k in range(x + 1, n - 1):
		c.append(s[k])
		c.append(s[k])
	c.append(s[n - 1])
	f = False
	for z in range(m):
		if c[z] != l[z]:
			f = True
			break
	if f == False:
		print(*s)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	m = 2 * n
	s = list(set(arr))
	cmp = []
	if len(s) != n:
		print(-1)
		continue
	arr.sort()
	mid = n // 2 - 1 if n % 2 == 0 else n // 2
	s.sort()
	for i in range(mid):
		cmp.append(s[i])
		cmp.append(s[i])
	cmp.append(s[mid])
	cmp.append(s[mid])
	cmp.append(s[mid])
	for i in range(mid + 1, n - 1):
		cmp.append(s[i])
		cmp.append(s[i])
	cmp.append(s[n - 1])
	flag = False
	for i in range(m):
		if cmp[i] != arr[i]:
			flag = True
			break
	if flag == False:
		print(*s)
	else:
		print(-1)


import sys
input = sys.stdin.readline
from collections import Counter
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	n = int(input())
	arr = [int(x) for x in input().strip().split()]
	if n == 1:
		if arr[0] == arr[1]:
			print(arr[0])
		else:
			print(-1)
		continue
	arr.sort()
	count = Counter(arr)
	if len(count) != n:
		print(-1)
		continue
	elements = sorted(count)
	ans = []
	is_possible = True
	i_mid = (n - 1) // 2
	for i in range(i_mid):
		if count[elements[i]] == 2:
			ans += [elements[i]]
		else:
			is_possible = False
			break
	if count[elements[i_mid]] == 3:
		ans += [elements[i_mid]]
	else:
		is_possible = False
	if not is_possible:
		print(-1)
		continue
	for i in range(i_mid + 1, n - 1):
		if count[elements[i]] == 2:
			ans += [elements[i]]
		else:
			is_possible = False
			break
	if count[elements[-1]] == 1:
		ans += [elements[-1]]
	else:
		is_possible = False
	if is_possible:
		print(*ans)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		d[i] = d.get(i, 0) + 1
	m = sorted(d)
	x = True
	if n == 1:
		for i in set(l):
			print(i)
	else:
		for i in range(len(m)):
			if n % 2 == 1:
				mid = n // 2
			else:
				mid = n // 2 - 1
			if i != mid and i != n - 1:
				if d[m[i]] != 2:
					print(-1)
					x = False
					break
			elif i == mid:
				if d[m[i]] != 3:
					print(-1)
					x = False
					break
			elif d[m[i]] != 1:
				print(-1)
				x = False
				break
		if x:
			for i in m:
				print(i, end=' ')
			print()


def ans(b):
	b.sort()
	x = max(b)
	a = []
	if len(b) == 2 and b.count(x) == 2:
		a.append(x)
		return a
	if b.count(x) != 1:
		return -1
	else:
		i = 0
		while i < len(b) - 1:
			if b[i] == b[i + 1]:
				if b[i] == b[i + 2]:
					if len(b) % 4 == 0:
						mp = len(b) // 4 - 1
					else:
						mp = len(b) // 4
					if len(a) == mp:
						a.append(b[i])
						i += 3
					else:
						return -1
				else:
					a.append(b[i])
					i += 2
			else:
				return -1
		a.append(max(b))
		if len(a) != len(b) / 2:
			return -1
		return a
for i in range(int(input())):
	ul = input()
	ints = input()
	b = []
	for x in ints.split():
		b.append(int(x))
	a = ans(b)
	if a == -1:
		print(-1)
	else:
		o = ''
		for x in a:
			o += str(x) + ' '
		print(o)


import math

def pre(l):
	ans = []
	for i in range(len(l)):
		if i == 0:
			ans.append(l[i])
		else:
			q = int(i / 2)
			p = l[q]
			ans.append(p)
	return ans

def suf(l):
	ans2 = []
	for i in range(1, len(l) + 1):
		if i % 2 != 0:
			p = int(math.ceil(i / 2))
			q = l[-p]
			ans2.append(q)
		else:
			p = int(i / 2) + 1
			q = l[-p]
			ans2.append(q)
	return ans2
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	test = []
	for i in set(l):
		test.append(i)
	test.sort()
	a = pre(test)
	b = suf(test)
	final_ans = a + b
	l.sort()
	final_ans.sort()
	if l != final_ans:
		print(-1)
	else:
		print(*test)


from collections import Counter
MOD = 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	a = sorted(list(set(b)))
	cnt = dict(Counter(b))
	if n == 1:
		print(a[0] if b == a * 2 else -1)
	else:
		med = (n - 1) // 2
		if any((cnt[el] != 2 for el in a[:med])) or cnt[a[med]] != 3 or cnt[a[-1]] != 1 or any((cnt[el] != 2 for el in a[med + 1:-1])):
			print(-1)
		else:
			print(' '.join(list(map(str, a))))


from collections import deque
for tc in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	se = set()
	dis = dict()
	for x in ls:
		if dis.get(x) is None:
			dis[x] = 1
		else:
			dis[x] += 1
		se.add(x)
	se = sorted(list(se))
	ln = 0
	dip = dict()
	const = []
	for x in se:
		const.append(x)
		ln += 1
		if ln % 2 == 0:
			med = const[ln // 2 - 1]
		else:
			med = const[ln // 2]
		if dip.get(med) is None:
			dip[med] = 1
		else:
			dip[med] += 1
	que = deque()
	ln = 0
	for x in range(len(se) - 1, -1, -1):
		que.appendleft(se[x])
		ln += 1
		if ln % 2 == 0:
			med = que[ln // 2 - 1]
		else:
			med = que[ln // 2]
		if dip.get(med) is None:
			dip[med] = 1
		else:
			dip[med] += 1
	fl = False
	for x in dip:
		if dip[x] != dis[x]:
			fl = True
			break
	if fl:
		print(-1)
	else:
		print(*se)


import sys
import math
from math import gcd, sqrt
import heapq as hq
from bisect import bisect_right, bisect_left, bisect
import itertools
from sys import stdin, stdout, setrecursionlimit

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def Median(a):
	n = len(a)
	if n % 2 == 0:
		return a[n // 2 - 1]
	else:
		return a[n // 2]
T = 1
T = int(stdin.readline())
MOD = int(1000000000.0) + 7
for _ in range(T):
	n = int(stdin.readline())
	b = list(map(int, stdin.readline().rstrip().split()))
	d = {}
	for i in range(2 * n):
		if b[i] not in d:
			d[b[i]] = 1
	a = list(d.keys())
	a.sort()
	if len(a) != n:
		print(-1)
		continue
	B = []
	for i in range(n):
		B.append(Median(a[:i + 1]))
	for i in range(n - 1, -1, -1):
		B.append(Median(a[i:]))
	B.sort()
	b.sort()
	if B == b:
		print(*a)
	else:
		print(-1)


from collections import Counter
T = int(input())
i = 1
while i <= T:
	i += 1
	N = int(input())
	nums = list(map(int, input().split()))
	distinct_nums = list(set(nums))
	c_distinct_nums = len(distinct_nums)
	if c_distinct_nums != N:
		print(-1)
	else:
		distinct_nums.sort()
		counter = dict(Counter(nums))
		median_pos = (N - 1) // 2
		end_pos = N - 1
		j = 0
		while j < N:
			if j == median_pos and j != end_pos:
				count = 3
			elif j != median_pos and j == end_pos:
				count = 1
			else:
				count = 2
			if counter[distinct_nums[j]] != count:
				print(-1)
				break
			j += 1
		if j == N:
			print(*distinct_nums)


import math

def rapidReOrdering(n, arr):
	mapDictX = {}
	for item in arr:
		mapDictX[item] = mapDictX.get(item, 0) + 1
	ansArr = sorted(mapDictX.keys())
	medianIdx = math.ceil(n / 2)
	for (idx, val) in enumerate(ansArr):
		if idx == n - 1:
			if mapDictX[val] != 1:
				return -1
		elif idx == medianIdx - 1:
			if mapDictX[val] != 3:
				return -1
		elif mapDictX[val] != 2:
			return -1
	return ansArr
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split(' ')))
	if n == 1:
		if arr[0] == arr[1]:
			print(arr[0])
		else:
			print(-1)
	else:
		ans = rapidReOrdering(n, arr)
		if ans == -1:
			print(-1)
		else:
			for i in ans:
				print(i, end=' ')
			print()


def validarraycount(n):
	L = [2 for i in range(n)]
	midindex = n // 2
	if n % 2:
		midindex += 1
	L[midindex - 1] = 3
	L[n - 1] = 1
	return L
for tc in range(int(input())):
	n = int(input())
	t = list(map(int, input().split()))
	if len(t) == 2:
		print(t[0]) if t[0] == t[1] else print(-1)
		continue
	x = []
	A = []
	t.sort()
	i = 0
	while i < 2 * n:
		count = 1
		j = i + 1
		while j < 2 * n:
			if t[j] == t[i]:
				count += 1
				j += 1
			else:
				break
		x.append(count)
		A.append(t[i])
		i = j
	y = validarraycount(n)
	if len(A) != n:
		print(-1)
	elif x == y:
		print(*A)
	else:
		print(-1)


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	a = list(map(int, input().split()))
	d = dict()
	for i in a:
		if d.get(i):
			d[i] = d[i] + 1
		else:
			d[i] = 1
	a1 = sorted(d)
	flag = 0
	if n == 1:
		if len(a1) != 1:
			flag = 1
		elif d[a1[0]] != 2:
			flag = 1
	else:
		for i in range(n):
			if i == n - 1:
				if d[a1[i]] != 1:
					flag = 1
					break
			elif (n - 1) // 2 == i:
				if d[a1[i]] != 3:
					flag = 1
					break
			elif d[a1[i]] != 2:
				flag = 1
				break
	if flag == 0:
		for i in a1:
			print(i, end=' ')
		print()
	else:
		print('-1')


from collections import defaultdict
from sys import stdin, stdout, setrecursionlimit
(readline, writeline) = (stdin.readline, stdout.write)
setrecursionlimit(100005)
for _ in range(int(readline())):
	n = int(input())
	lst = list(map(int, readline().split()))
	lst.sort()
	s = set()
	arr = []
	for i in lst:
		if i not in s:
			arr.append(i)
			s.add(i)
	if len(s) != n:
		print(-1)
		continue
	arr1 = [arr[0]]
	l = len(arr)
	for i in range(1, l):
		arr1.append(arr[i // 2])
	for i in range(l):
		arr1.append(arr[(i + l - 1) // 2])
	if lst == arr1:
		print(*arr)
	else:
		print(-1)


try:
	for t in range(int(input())):
		N = int(input())
		B = list(map(int, input().split()))
		B.sort()
		A = list(set(B))
		A.sort()
		pos = (len(A) - 1) // 2
		dic = {}
		if N == 1:
			if len(A) == 1:
				print(B[0])
				continue
			else:
				print(-1)
				continue
		for element in B:
			if element not in dic:
				dic[element] = 0
			dic[element] += 1
		val = list(dic.values())
		if len(dic) == N:
			if dic.get(A[pos]) == 3 and dic.get(A[-1]) == 1 and (val.count(2) == len(A) - 2):
				print(*A)
			else:
				print(-1)
		else:
			print(-1)
except:
	pass


def mod_inv(a):
	return pow(a, MOD - 2, MOD)
import io, os, sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def Q1(S, A, B, C):
	p = S * (1 + C / 100)
	return 'YES' if p >= A and p <= B else 'NO'

def Q2(N, K):

	def hcf(x, y):
		return hcf(y, x % y) if y else x
	return N // hcf(N, K)
MOD = 998244353
Q_inv = mod_inv(4)

def Q3(N):
	return N * pow(N + 1, 2, MOD) * Q_inv % MOD

def Q4(N, B):
	B.sort()
	count = dict()
	for b in B:
		if b not in count:
			count[b] = 1
		else:
			count[b] += 1
	even = sum((1 for x in count if not count[x] % 2))
	if N == 1:
		return [B[0]] if B[0] == B[1] else [-1]
	else:
		m = N - 1 if N % 2 else N - 2
		if (B[m] != B[m + 1] or B[m] != B[m + 2] or count[B[m]] != 3) or B[-1] == B[-2] or even != N - 2:
			return [-1]
		else:
			return [B[2 * i + 1] for i in range(N - 1)] + [B[-1]]
for _ in range(inp()):
	N = inp()
	B = inlt()
	outlt(Q4(N, B))


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	b.sort()
	seti = list(set(b))
	seti.sort()
	c = Counter(b)
	if n % 2 == 0:
		mid = n // 2 - 1
	else:
		mid = n // 2
	is_valid = True
	if n == 1:
		if c[seti[0]] != 2:
			is_valid = False
	elif len(seti) == n:
		if c[seti[mid]] != 3:
			is_valid = False
		if c[seti[-1]] != 1:
			is_valid = False
		for i in range(n - 1):
			if i != mid:
				if c[seti[i]] != 2:
					is_valid = False
	else:
		is_valid = False
	if is_valid:
		print(*seti)
	else:
		print(-1)


t = int(input())
while t > 0:
	n = int(input()) * 2
	lst = list(map(int, input().split()))
	sett = list(set(lst))
	ans = []
	sett.sort()
	for i in range(len(sett)):
		ans.append(sett[i // 2])
		ans.append(sett[(len(sett) - 1 + i) // 2])
	ans.sort()
	lst.sort()
	if ans == lst:
		print(*sett)
	else:
		print(-1)
	t -= 1


t = int(input())

def f(l):
	n = len(l) // 2
	s = set(l)
	d = {}
	if len(s) == 1 and len(l) == 2:
		return [l[0]]
	if n == len(s):
		a = sorted(list(s))
		for j in s:
			d[j] = 0
		for k in l:
			d[k] += 1
		if n % 2 == 0:
			m = n // 2 - 1
		else:
			m = n // 2
		for x in range(n):
			if x == m:
				if d[a[x]] != 3:
					return [-1]
			elif x == n - 1:
				if d[a[x]] != 1:
					return [-1]
			elif d[a[x]] != 2:
				return [-1]
		return a
	return [-1]
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	y = list(map(str, f(l)))
	print(' '.join(y))


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	lst.sort()
	a = list(set(lst))
	a.sort()
	ns = []
	for j in range(1, len(a) + 1):
		if j % 2 != 0:
			k = a[j // 2]
			ns.append(k)
		else:
			k = a[j // 2 - 1]
			ns.append(k)
	r = a[::-1]
	for j in range(1, len(a) + 1):
		if j % 2 != 0:
			k = r[j // 2]
			ns.append(k)
		else:
			k = r[j // 2]
			ns.append(k)
	ns.sort()
	if ns == lst:
		g = list(set(ns))
		g.sort()
		print(*g)
	else:
		print('-1')


import math

def find_median(l):
	if len(l) % 2 == 0:
		return l[len(l) // 2 - 1]
	else:
		return l[math.floor(len(l) / 2)]
try:
	t = int(input())
	while t > 0:
		t -= 1
		n = int(input())
		b = list(map(int, input().split(' ')))
		a = list(set(b))
		a.sort()
		b.sort()
		ans = []
		for i in range(1, len(a) + 1):
			ans.append(find_median(a[:i]))
		for i in range(1, len(a) + 1):
			ans.append(find_median(a[-i:]))
		ans.sort()
		if ans == b:
			for i in a:
				print(i, end=' ')
			print()
		else:
			print(-1)
except:
	pass


from math import ceil, floor

def median(a):
	n = len(a)
	index = floor(n / 2) if n % 2 != 0 else n // 2 - 1
	return a[index]
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split(' ')))
	bFreq = {}
	aFreq = {}
	for i in range(2 * n):
		bFreq[b[i]] = bFreq.get(b[i], 0) + 1
	a = list(bFreq.keys())
	a.sort()
	n2 = len(a)
	for pre in range(1, n2 + 1):
		_median = median(a[:pre])
		aFreq[_median] = aFreq.get(_median, 0) + 1
		_median = median(a[-pre:])
		aFreq[_median] = aFreq.get(_median, 0) + 1
	f = 1
	for (k, v) in aFreq.items():
		if bFreq[k] == v:
			pass
		else:
			f = 0
			break
	print((-1, ' '.join(list(map(str, a))))[f])


for i in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	a = list(set(b))
	c = []
	a.sort()
	for i in range(len(a)):
		c.append(a[i // 2])
		c.append(a[(len(a) - 1 + i) // 2])
	c.sort()
	b.sort()
	if c == b:
		print(*a)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		if len(set(a)) == 1:
			print(a[0])
		else:
			print(-1)
	else:
		d = {}
		for i in range(2 * n):
			if a[i] not in d:
				d[a[i]] = 0
			d[a[i]] += 1
		ke = list(d.keys())
		ke.sort()
		c = []
		for i in range(len(ke)):
			c.append(d[ke[i]])
		ans = 1
		if len(ke) == n:
			l = (len(ke) - 1) // 2
			for i in range(n):
				if i == l:
					if c[i] != 3:
						ans = 0
						break
				elif i == n - 1:
					if c[i] != 1:
						ans = 0
						break
				elif c[i] != 2:
					ans = 0
					break
			if ans:
				print(*ke)
			else:
				print(-1)
		else:
			print(-1)


from collections import Counter

def checksforTwo(b):
	a = sorted(list(set(b)))
	ans = 0
	if b.count(min(a)) != 3:
		ans = -1
	if b.count(max(a)) != 1:
		ans = -1
	if ans != -1:
		return a
	else:
		return [-1]

def checksforThreeMore(b):
	ans = 0
	c = Counter(b)
	twiceOnes = list(filter(lambda x: c[x] == 2, c))
	s = sorted(list(set(b)))
	median = s[(len(s) - 1) // 2]
	if c[median] != 3:
		ans = -1
	if c[max(b)] != 1:
		ans = -1
	if len(twiceOnes) != n - 2:
		ans = -1
	if ans != -1:
		ans = sorted(s)
	else:
		ans = [-1]
	return ans
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	if n == 1:
		if b[0] == b[1]:
			res = [b[0]]
		else:
			res = [-1]
	elif n == 2:
		res = checksforTwo(b)
	else:
		res = checksforThreeMore(b)
	print(*res)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	c = Counter(arr)
	m = max(arr)
	if n == 1:
		if arr[0] == arr[1]:
			print(arr[0])
		else:
			print(-1)
		continue
	mid = n // 2 if n % 2 else n // 2 - 1
	f = 1
	if c[m] != 1:
		print(-1)
	else:
		ans = []
		i = 0
		for el in sorted(c):
			if f == 0:
				break
			if i != mid and i != n - 1:
				if c[el] != 2:
					print(-1)
					f = 0
					break
			elif i == mid:
				if c[el] != 3:
					print(-1)
					f = 0
					break
			ans.append(el)
			i += 1
		if f == 1:
			print(*ans)


from collections import Counter
t = int(input())
while t != 0:
	n = int(input())
	b = list(map(int, input().split()))
	a = list(set(b))
	a.sort()
	counts = dict(Counter(b))
	if n == 1 and b[0] == b[1]:
		print(b[0])
	else:
		if n % 2 == 0:
			mid = n // 2 - 1
		else:
			mid = n // 2
		isValid = True
		for (value, count) in counts.items():
			if value == a[mid]:
				if count != 3:
					isValid = False
					break
			elif value == a[-1]:
				if count != 1:
					isValid = False
					break
			elif count != 2:
				isValid = False
				break
		a = [str(i) for i in a]
		if isValid:
			print(' '.join(a))
		else:
			print(-1)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	mid = (n - 1) // 2
	if n == 1:
		if lst[0] == lst[1]:
			print(lst[0])
		else:
			print(-1)
	else:
		d = {}
		for i in range(n * 2):
			if lst[i] not in d:
				d[lst[i]] = 1
			else:
				d[lst[i]] += 1
		ele = list(sorted(d.keys()))
		if len(ele) != n:
			print(-1)
		else:
			for i in range(n):
				if i == mid:
					if d[ele[i]] != 3:
						print(-1)
						break
				elif i == n - 1:
					if d[ele[i]] != 1:
						print(-1)
						break
				elif d[ele[i]] != 2:
					print(-1)
					break
			else:
				print(*ele)


for tc in range(int(input())):
	n = int(input())
	se = set()
	dis = dict()
	ls = list(map(int, input().split()))
	for x in ls:
		if dis.get(x) is None:
			dis[x] = 1
		else:
			dis[x] += 1
		se.add(x)
	pn = sorted(list(se))
	if len(pn) == 1:
		if dis[pn[0]] == 2:
			print(*pn)
		else:
			print(-1)
	else:
		mid = len(pn) // 2
		if len(pn) % 2 == 0:
			mid -= 1
		(a, b) = (pn[mid], pn[-1])
		res = True
		for x in dis:
			if x == a:
				if dis[x] == 3:
					pass
				else:
					res = False
					break
			elif x == b:
				if dis[x] == 1:
					pass
				else:
					res = False
					break
			elif dis[x] == 2:
				pass
			else:
				res = False
				break
		if res:
			print(*pn)
		else:
			print(-1)


import math
t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	if n == 1:
		if len(set(lst)) != 1:
			print(-1)
		else:
			print(lst[0])
	else:
		s = set(lst)
		lstf = list(s)
		lstf.sort()
		l = len(lstf)
		if l % 2 == 0:
			med = lstf[l // 2 - 1]
		else:
			med = lstf[l // 2]
		m = max(lstf)
		a = 0
		if lst.count(med) == 3 and lst.count(m) == 1:
			a += 1
		if a == 0:
			print(-1)
		else:
			lst.sort()
			lst.remove(med)
			lst.remove(med)
			lst.remove(med)
			lst.remove(m)
			c2 = 0
			if len(lst) % 2 != 0:
				print(-1)
			else:
				for g in range(0, len(lst), 2):
					if lst[g] == lst[g + 1]:
						c2 += 1
				if c2 == (2 * n - 4) // 2:
					print(*lstf)
				else:
					print(-1)


from sys import stdin
from collections import Counter

def check1(arr):
	new_dict = {}
	for i in range(len(arr)):
		temp = arr[:i + 1]
		if len(temp) % 2 == 0:
			value = len(temp) // 2
			value -= 1
			median = arr[value]
		else:
			value = len(temp) // 2
			median = arr[value]
		if median not in new_dict:
			new_dict[median] = 1
		else:
			new_dict[median] += 1
	return new_dict

def check2(arr):
	new_dict = {}
	for i in range(len(arr) - 1, -1, -1):
		temp = arr[i:]
		if len(temp) % 2 == 0:
			value = len(temp) // 2
			value -= 1
			median = temp[value]
		else:
			value = len(temp) // 2
			median = temp[value]
		if median not in new_dict:
			new_dict[median] = 1
		else:
			new_dict[median] += 1
	return new_dict
t = int(stdin.readline().rstrip())
while t > 0:
	n = int(stdin.readline().rstrip())
	b = list(map(int, stdin.readline().strip().split(' ')[:2 * n]))
	my_dict = Counter(b)
	s = set(b)
	arr = list(s)
	arr.sort()
	dict1 = check1(arr)
	dict2 = check2(arr)
	l1 = [0] * (max(arr) + 1)
	for (key, item) in dict1.items():
		l1[key] += item
	for (key, item) in dict2.items():
		l1[key] += item
	flag = True
	for (key, item) in my_dict.items():
		if item == l1[key]:
			flag = True
		else:
			flag = False
			break
	if flag:
		print(*arr)
	else:
		print(-1)
	t -= 1


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = defaultdict(lambda : 0)
	for i in l:
		d[i] += 1
	new = []
	for i in d.keys():
		new.append(i)
	new.sort()
	if len(new) != n:
		print(-1)
	else:
		z = []
		for i in range(n):
			z.append(new[i // 2])
		s = new[::-1]
		for j in range(n):
			z.append(s[j // 2 + j % 2])
		if sorted(z) == sorted(l):
			print(*new)
		else:
			print(-1)


from sys import stdin, stdout
inp_num = lambda : int(input())
inp_lis = lambda : list(map(int, input().split()))
for _ in range(inp_num()):
	n = inp_num()
	l = inp_lis()
	l1 = list(set(l))
	if len(l1) != n:
		print(-1)
		continue
	if len(l1) == 1 and n == 1:
		print(*l1)
		continue
	l1.sort()
	dic = {}
	for i in l1:
		dic[i] = 0
	for i in l:
		dic[i] += 1
	an = 1
	for i in range(n):
		if i == int((n + 1) / 2) - 1:
			if dic[l1[i]] != 3:
				an = 0
				break
			else:
				continue
		elif i == n - 1:
			if dic[l1[i]] != 1:
				an = 0
				break
			else:
				continue
		elif dic[l1[i]] == 2:
			continue
		else:
			an = 0
			break
	if an == 0:
		print(-1)
	else:
		print(*l1)


for i in range(int(input())):
	n = int(input())
	B = [int(j) for j in input().split()]
	A = set(B)
	l = []
	for k in A:
		l.append(k)
	l.sort()
	d = dict()
	for k in l:
		d[k] = 0
	for k in B:
		d[k] += 1
	z = 2
	if len(l) % 2 == 1:
		s = len(l) // 2
	else:
		s = (len(l) - 1) // 2
	m = []
	if n == 1:
		m.append(2)
	elif n == 2:
		m.append(3)
		m.append(1)
	else:
		for k in range(len(l)):
			if k == 0 and n != 1:
				m.append(2)
			elif k == 0 and n == 1:
				m.append(1)
			elif k == len(l) - 1:
				m.append(1)
			elif k == s:
				m.append(3)
			else:
				m.append(z)
	q = []
	for (k, v) in d.items():
		q.append(v)
	if q == m:
		for k in l:
			print(k, end=' ')
		print()
	else:
		print(-1)


t = int(input())
for z in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	if n == 1:
		print(b[0])
		continue
	b.sort()
	a = [-1] * n
	j = 0
	for i in range(1, 2 * n, 2):
		if i < n:
			if b[i] != b[i - 1]:
				print(-1)
				break
			if i != 1 and b[i] == b[i - 2]:
				print(-1)
				break
		elif i == n:
			if b[i] != b[i - 1] or b[i] != b[i + 1]:
				print(-1)
				break
			if b[i] == b[i - 2]:
				print(-1)
				break
		else:
			if i != 2 * n - 1 and b[i] != b[i + 1]:
				print(-1)
				break
			if b[i] == b[i - 1]:
				print(-1)
				break
		a[j] = b[i]
		j += 1
	else:
		for i in range(n):
			print(a[i], end=' ')
	print('')


from sys import stdin
input = stdin.readline

def answer():
	ans = sorted(list(set(b)))
	if len(ans) < n or len(ans) > n:
		return [-1]
	d = dict()
	for i in range(2 * n):
		d[b[i]] = d.get(b[i], 0) + 1
	for i in range(n):
		median = i // 2
		if d[ans[median]] == 0:
			return [-1]
		d[ans[median]] -= 1
	for i in range(n - 1, -1, -1):
		median = i + (n - i - 1) // 2
		if d[ans[median]] == 0:
			return [-1]
		d[ans[median]] -= 1
	return ans
for T in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	print(*answer())


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		if l[0] == l[1]:
			print(l[0])
			continue
		else:
			print(-1)
			continue
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	t = 0
	o = 0
	th = 0
	for i in d:
		if d[i] == 2:
			t += 1
		if d[i] == 1:
			o += 1
		if d[i] == 3:
			th += 1
	if o != 1 or th != 1 or t != n - 2:
		print(-1)
	else:
		if n % 2 == 0:
			m = n // 2 - 1
		else:
			m = n // 2
		ans = [0] * n
		v = []
		for i in d:
			if d[i] == 1:
				ans[-1] = i
			if d[i] == 3:
				ans[m] = i
			if d[i] == 2:
				v.append(i)
		j = 0
		v.sort()
		for i in range(n):
			if ans[i] == 0:
				ans[i] = v[j]
				j += 1
		t = sorted(ans)
		f = 0
		for i in range(n):
			if ans[i] != t[i]:
				f = 1
		if f == 1:
			print(-1)
		else:
			print(*ans)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	suffix_array = []
	prefix_array = []
	A = sorted(list(set(l1)))
	n1 = len(A)
	d1 = {}
	for i in l1:
		if i in d1.keys():
			d1[i] += 1
		else:
			d1[i] = 1
	for i in range(n1):
		if (i + 1) % 2 == 0:
			suffix_array.append(A[i // 2])
			x = (2 * n1 - i - 2) // 2
			prefix_array.append(A[x])
		else:
			suffix_array.append(A[(i + 1) // 2])
			x = (2 * n1 - i - 2) // 2 + 1
			prefix_array.append(A[x - 1])
	for i in suffix_array:
		if i in d1.keys():
			d1[i] -= 1
	for i in prefix_array:
		if i in d1.keys():
			d1[i] -= 1
	flag = False
	for i in d1.keys():
		if d1[i] > 0:
			print(-1)
			flag = True
			break
	if flag == False:
		print(*A)


from collections import defaultdict
t = int(input())
while t:
	t -= 1
	n = int(input())
	frq = defaultdict(int)
	b = list(map(int, input().split(' ')))
	for i in b:
		frq[i] += 1
	if n == 1:
		if b[0] == b[1]:
			print(b[0])
		else:
			print(-1)
		continue
	uniq = sorted(list(frq.keys()))
	if len(uniq) != n:
		print(-1)
		continue
	med = uniq[(n - 1) // 2]
	last = uniq[n - 1]
	ok = True
	if frq[med] != 3 or frq[last] != 1:
		ok = False
	for i in range(n - 1):
		if i != (n - 1) // 2 and frq[uniq[i]] != 2:
			ok = False
	if ok:
		print(' '.join(map(str, uniq)))
	else:
		print(-1)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	di = {}
	for i in range(2 * n):
		if a[i] in di.keys():
			di[a[i]] += 1
		else:
			di[a[i]] = 1
	d = set(a)
	d = list(d)
	d.sort()
	if len(d) != n:
		print('-1')
	elif n == 1:
		print(d[0])
	else:
		k = d[(n - 1) // 2]
		f = True
		for i in range(n):
			if i == (n - 1) // 2:
				if di[d[i]] != 3:
					print('-1')
					f = False
					break
			elif i == n - 1:
				if di[d[i]] != 1:
					print('-1')
					f = False
					break
			elif di[d[i]] != 2:
				print('-1')
				f = False
				break
		if f == True:
			print(' '.join(map(str, d)))
	t = t - 1


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	m = Counter(b)
	a = list(set(b))
	if len(a) != n:
		print(-1)
		continue
	if n == 1:
		print(*a)
		continue
	a.sort()
	exp = [2] * n
	exp[(n - 1) // 2] = 3
	exp[-1] = 1
	ok = True
	for i in range(n):
		if m[a[i]] != exp[i]:
			ok = False
			break
	if ok:
		print(*a)
	else:
		print(-1)


def funcx(n, l2):
	d1 = {}
	if n == 1:
		if l2[0] == l2[1]:
			print(l2[0])
			return
		else:
			print(-1)
			return
	for i in l2:
		d1[i] = d1.get(i, 0) + 1
	l1 = list(d1.keys())
	l1.sort()
	if len(l1) != n:
		print(-1)
		return
	if d1[l1[-1]] != 1:
		print(-1)
		return
	for i in range(n - 1):
		if n % 2 == 1:
			if i == n // 2:
				if d1[l1[i]] != 3:
					print(-1)
					return
			elif d1[l1[i]] != 2:
				print(-1)
				return
		elif i == n // 2 - 1:
			if d1[l1[i]] != 3:
				print(-1)
				return
		elif d1[l1[i]] != 2:
			print(-1)
			return
	print(*l1)
	return
t = int(input())
for i in range(t):
	n = int(input())
	l1 = [int(i) for i in input().split()]
	funcx(n, l1)


from collections import defaultdict
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	d = defaultdict(lambda : 0)
	for i in range(2 * N):
		d[A[i]] += 1
	ans = [0] * N
	ll = list(d.keys())
	l = list(d.values())
	if N == 1:
		if A[0] == A[-1]:
			print(A[0])
		else:
			print(-1)
	elif N == 2:
		if d[ll[0]] == 3 and d[ll[1]] == 1 or (d[ll[0]] == 1 and d[ll[1]] == 3):
			if d[ll[0]] == 3:
				print(ll[0], ll[1])
			else:
				print(ll[1], ll[0])
		else:
			print(-1)
	elif N > 2:
		if l.count(1) != 1:
			print(-1)
		elif l.count(3) != 1:
			print(-1)
		elif l.count(2) != N - 2:
			print(-1)
		else:
			j = 0
			dd = ll
			dd.sort()
			if N % 2 != 0:
				for i in dd:
					if d[i] == 2:
						if j == N // 2:
							j += 1
						ans[j] = i
						j += 1
					if d[i] == 3:
						ans[N // 2] = i
					if d[i] == 1:
						ans[-1] = i
			else:
				for i in dd:
					if d[i] == 2:
						if j == N // 2 - 1:
							j += 1
						ans[j] = i
						j += 1
					if d[i] == 3:
						ans[N // 2 - 1] = i
					if d[i] == 1:
						ans[-1] = i
			k = sorted(ans)
			if k == ans:
				print(*ans)
			else:
				print(-1)


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	d = {}
	for i in b:
		try:
			if d[i]:
				d[i] += 1
		except KeyError:
			d[i] = 1
	if len(d) != n:
		print(-1)
	elif n == 1:
		print(b[-1])
	else:
		a = []
		for i in d:
			a.append(i)
		a.sort()
		if n == 2:
			if d[a[0]] == 3 and d[a[1]] == 1:
				print(a[0], end=' ')
				print(a[1])
			else:
				print(-1)
			continue
		f = 0
		if n % 2 == 0:
			for i in range(n // 2 - 1):
				if d[a[i]] != 2:
					f = 1
					break
			if f == 1:
				print(-1)
				continue
			for i in range(n // 2, n - 1):
				if d[a[i]] != 2:
					f = 1
					break
			if f == 1:
				print(-1)
				continue
			if d[a[-1]] == 1 and d[a[n // 2 - 1]] == 3:
				for i in range(n):
					print(a[i], end=' ')
				print()
				continue
			else:
				print(-1)
				continue
		else:
			for i in range(n // 2):
				if d[a[i]] != 2:
					f = 1
					break
			if f == 1:
				print(-1)
				continue
			for i in range(n // 2 + 1, n - 1):
				if d[a[i]] != 2:
					f = 1
					break
			if f == 1:
				print(-1)
				continue
			if d[a[-1]] == 1 and d[a[n // 2]] == 3:
				for i in range(n):
					print(a[i], end=' ')
				print()
				continue
			else:
				print(-1)
				continue


import math
t = int(input())
for _ in range(t):
	n = int(input())
	b = [int(x) for x in input().split()]
	has = {}
	for i in b:
		if i not in has:
			has[i] = 1
		else:
			has[i] += 1
	flag = True
	res = {}
	for i in range(n):
		t = i // 2
		if t not in res:
			res[t] = 1
		else:
			res[t] += 1
	for i in range(n - 1, -1, -1):
		t = math.ceil((n - 1 + i) // 2)
		if t not in res:
			res[t] = 1
		else:
			res[t] += 1
	pre = sorted(list(set(b)))

	def solve(has, res, pre):
		for i in range(len(pre)):
			if has[pre[i]] == res[i]:
				continue
			else:
				print(-1)
				return
		print(*pre)
		return
	solve(has, res, pre)


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	l1 = set(l)
	l1 = sorted(l1)
	flag = 1
	if n == 1:
		if len(l1) != 1:
			flag = 0
	elif l.count(l1[-1]) == 1:
		mid = int((n - 1) / 2)
		if l.count(l1[mid]) == 3:
			for i in l1:
				if i != l1[-1] and i != l1[mid]:
					if l.count(i) != 2:
						flag = 0
						break
		else:
			flag = 0
	else:
		flag = 0
	if flag:
		for i in l1:
			print(i, end=' ')
		print()
	else:
		print(-1)


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	c = Counter(b)
	if n == 1:
		if len(set(b)) == 2:
			print(-1)
		else:
			print(b[0])
		continue
	ck = list(c.keys())
	cv = list(c.values())
	se = list(set(b))
	se.sort()
	if len(se) < n:
		print(-1)
		continue
	dick = dict(zip(ck, cv))
	if len(se) % 2 == 0:
		mid = len(se) // 2 - 1
	else:
		mid = len(se) // 2
	if n >= 3:
		if dick[se[-1]] == 1 and dick[se[mid]] == 3 and (cv.count(2) == n - 2):
			print(*se)
		else:
			print(-1)
	elif n == 2:
		if dick[se[-1]] == 1 and dick[se[mid]] == 3:
			print(*se)
		else:
			print(-1)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	if n == 1 and lst[0] == lst[1]:
		print(lst[0])
	else:
		lst.sort()
		dic = defaultdict(lambda : 0)
		for i in lst:
			dic[i] += 1
		arr = sorted(list(dic.keys()))
		if n % 2 == 0:
			x = arr[n // 2 - 1]
			y = arr[-1]
			for i in dic.keys():
				if i == x and dic[i] != 3:
					print(-1)
					break
				elif i == y and dic[i] != 1:
					print(-1)
					break
				elif i != x and i != y and (dic[i] != 2):
					print(-1)
					break
			else:
				print(*arr)
		else:
			x = arr[n // 2]
			y = arr[-1]
			for i in dic.keys():
				if i == x and dic[i] != 3:
					print(-1)
					break
				elif i == y and dic[i] != 1:
					print(-1)
					break
				elif i != x and i != y and (dic[i] != 2):
					print(-1)
					break
			else:
				print(*arr)


t = int(input())

def median(a):
	return a[(len(a) + 1) // 2 - 1]
for _ in range(t):
	n = int(input())
	medians = [int(x) for x in input().split()]
	elements = set()
	for x in medians:
		elements.add(x)
	elements = list(elements)
	elements.sort()
	medians.sort()
	flag = True
	for i in range(n):
		m1 = median(elements[:i + 1])
		m2 = median(elements[-(i + 1):])
		if m1 != medians[i] or m2 != medians[-(i + 1)]:
			flag = False
			break
	if len(elements) != n:
		print(-1)
		continue
	if flag:
		for x in elements:
			print(x, end=' ')
		print()
	else:
		print(-1)


for _ in range(int(input())):
	int(input())
	arr = list(map(int, input().split()))
	ar1 = set(arr)
	ar1 = list(ar1)
	ar1.sort()
	try:
		ind = 0
		for i in range(1, len(ar1) + 1):
			arr.remove(ar1[ind])
			if i % 2 == 0:
				ind += 1
		ar1.reverse()
		ind = 0
		for i in range(len(ar1)):
			arr.remove(ar1[ind])
			if i % 2 == 0:
				ind += 1
		if len(arr) == 0:
			ar1.reverse()
			for i in ar1:
				print(i, end=' ')
			print()
		else:
			print(-1)
	except:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	s = set()
	arr.sort()
	for i in arr:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
			s.add(i)
	ss = []
	ans = True
	for i in s:
		ss.append(i)
	if n == 1:
		print(*ss)
		continue
	maxm = max(ss)
	l = len(ss)
	ss.sort()
	if d[maxm] != 1:
		print(-1)
		ans = False
	else:
		d[maxm] = 0
		if l % 2 == 0:
			temp = l // 2 - 1
		else:
			temp = l // 2
		if d[ss[temp]] != 3:
			ans = False
			print(-1)
		else:
			d[ss[temp]] = 0
			for i in d:
				if d[i] != 2 and d[i] != 0:
					print(-1)
					ans = False
					break
	if ans == True:
		if n != l:
			print(-1)
		else:
			print(*ss)