Monocarp is a little boy who lives in Byteland and he loves programming.

Recently, he found a permutation of length $n$. He has to come up with a mystic permutation. It has to be a new permutation such that it differs from the old one in each position.

More formally, if the old permutation is $p_1,p_2,\ldots,p_n$ and the new one is $q_1,q_2,\ldots,q_n$ it must hold that $$p_1\neq q_1, p_2\neq q_2, \ldots ,p_n\neq q_n.$$

Monocarp is afraid of lexicographically large permutations. Can you please help him to find the lexicographically minimal mystic permutation?


-----Input-----

There are several test cases in the input data. The first line contains a single integer $t$ ($1\leq t\leq 200$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains a positive integer $n$ ($1\leq n\leq 1000$) — the length of the permutation.

The second line of each test case contains $n$ distinct positive integers $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n$). It's guaranteed that $p$ is a permutation, i. e. $p_i \neq p_j$ for all $i \neq j$.

It is guaranteed that the sum of $n$ does not exceed $1000$ over all test cases.


-----Output-----

For each test case, output $n$ positive integers — the lexicographically minimal mystic permutations. If such a permutation does not exist, output $-1$ instead.


-----Examples-----

Input
4
3
1 2 3
5
2 3 4 5 1
4
2 3 1 4
1
1
Output
2 3 1
1 2 3 4 5
1 2 4 3
-1


-----Note-----

In the first test case possible permutations that are mystic are $[2,3,1]$ and $[3,1,2]$. Lexicographically smaller of the two is $[2,3,1]$.

In the second test case, $[1,2,3,4,5]$ is the lexicographically minimal permutation and it is also mystic.

In third test case possible mystic permutations are $[1,2,4,3]$, $[1,4,2,3]$, $[1,4,3,2]$, $[3,1,4,2]$, $[3,2,4,1]$, $[3,4,2,1]$, $[4,1,2,3]$, $[4,1,3,2]$ and $[4,3,2,1]$. The smallest one is $[1,2,4,3]$.

Source: codeforces | Difficulty: EASY
Tags: Data structures

Greedy algorithms


Solutions:
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l2 = sorted(l)
	i = 0
	if n == 1:
		print(-1)
	else:
		for i in range(n):
			if l2[i] == l[i]:
				if i == n - 1:
					h = n - 2
					while h > 0 and l2[h] == l[h]:
						h -= 1
					(l2[i], l2[h]) = (l2[h], l2[i])
				else:
					(l2[i], l2[i + 1]) = (l2[i + 1], l2[i])
		print(*l2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	for i in range(1, n + 1):
		b.append(i)
	if n == 1:
		print(-1)
		continue
	for i in range(n):
		if a[i] != b[i]:
			continue
		if i == n - 1:
			(b[n - 1], b[n - 2]) = (b[n - 2], b[n - 1])
		else:
			(b[i], b[i + 1]) = (b[i + 1], b[i])
	print(*b)


for _ in range(int(input())):
	input()
	nums = list(map(int, input().split()))
	if len(nums) == 1:
		print(-1)
	else:
		sorted_nums = sorted(nums)
		i = 0
		while i < len(nums) - 1:
			if sorted_nums[i] == nums[i]:
				(sorted_nums[i], sorted_nums[i + 1]) = (sorted_nums[i + 1], sorted_nums[i])
				i += 1
			i += 1
		i = len(sorted_nums) - 1
		if sorted_nums[i] == nums[i]:
			(sorted_nums[i], sorted_nums[i - 1]) = (sorted_nums[i - 1], sorted_nums[i])
		print(' '.join(map(str, sorted_nums)))


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	ans = []
	if len(l) == 1:
		print(-1)
		t -= 1
		continue
	l1 = l[:]
	l1.sort()
	for i in range(len(l1) - 1):
		if l1[i] == l[i]:
			(l1[i], l1[i + 1]) = (l1[i + 1], l1[i])
	if l[-1] == l1[-1]:
		(l1[-1], l1[-2]) = (l1[-2], l1[-1])
	print(*l1)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(-1)
		continue
	else:
		l1 = l.copy()
		l1.sort()
		for i in range(n - 1):
			if l1[i] == l[i]:
				t = l1[i]
				l1[i] = l1[i + 1]
				l1[i + 1] = t
		if l1[n - 1] == l[n - 1]:
			t = l1[n - 2]
			l1[n - 2] = l1[n - 1]
			l1[n - 1] = t
	print(*l1)


import heapq
T = int(input())
while T:
	T -= 1
	N = int(input())
	init = list(map(int, input().split()))
	Number = [i for i in range(1, N + 1)]
	if N == 1:
		print(-1)
		continue
	ans = [None] * N
	for i in range(N):
		if Number[0] != init[i]:
			ans[i] = heapq.heappop(Number)
		elif len(Number) > 1:
			a = heapq.heappop(Number)
			ans[i] = heapq.heappop(Number)
			heapq.heappush(Number, a)
		else:
			a = heapq.heappop(Number)
			ans[i] = a
			(ans[i - 1], ans[i]) = (ans[i], ans[i - 1])
	for ele in ans:
		print(ele, end=' ')
	print()


def mystic_permutation(n, p):
	if len(p) == 1:
		return [-1]
	p_sorted = sorted(p, reverse=True)
	temp = None
	i = n - 1
	j = 0
	output = []
	while i >= 0:
		if temp is not None:
			output.append(temp)
			temp = None
			i -= 1
			j += 1
			continue
		element = p_sorted.pop()
		if p[j] == element:
			temp = element
			if len(p_sorted) == 0:
				output.append(temp)
				break
			output.append(p_sorted.pop())
		else:
			output.append(element)
		i -= 1
		j += 1
	if output[-1] == p[-1]:
		(output[-1], output[-2]) = (output[-2], output[-1])
		i -= 1
		j += 1
	for i in range(n):
		if p[i] == output[i]:
			return [-1]
	return output

def main():
	t = input()
	t = int(t)
	for i in range(t):
		n = input()
		n = int(n)
		p = list(map(int, input().split()))
		output = mystic_permutation(n, p)
		for o in output:
			print(o, end=' ')
		print()
main()


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		l = input()
		print(-1)
	else:
		l = list(map(int, input().split(' ')))
		s = sorted(l)
		ret = []
		for i in range(n - 1):
			if s[i] == l[i]:
				(s[i], s[i + 1]) = (s[i + 1], s[i])
		if s[-1] == l[-1]:
			(s[-1], s[-2]) = (s[-2], s[-1])
		print(*s)


def mystic_per(l):
	if len(l) == 1 or len(l) == 0:
		return [-1]
	m = l.copy()
	l.sort()
	i = 0
	while i < len(l) - 1:
		if l[i] == m[i]:
			(l[i], l[i + 1]) = (l[i + 1], l[i])
		i += 1
	if i == len(l) - 1:
		if l[i] == m[i]:
			(l[i], l[i - 1]) = (l[i - 1], l[i])
	return l
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(*mystic_per(l))


t = int(input())
for i in range(t):
	n = int(input())
	p = [int(x) for x in input().split()]
	p1 = []
	for q in range(n):
		p1.append(p[q])
	p.sort()
	if len(p) == 1:
		print(-1, end=' ')
	elif len(p) == 2:
		print(p1[1], end=' ')
		print(p1[0], end=' ')
	else:
		for j in range(n - 1):
			if p[j] == p1[j]:
				(p[j], p[j + 1]) = (p[j + 1], p[j])
		if p[n - 1] == p1[n - 1]:
			(p[n - 1], p[n - 2]) = (p[n - 2], p[n - 1])
		for k in range(n):
			print(p[k], end=' ')
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(-1)
		continue
	ref = [i for i in range(1, n + 1)]
	indexs = []
	for i in range(n):
		if arr[i] == ref[i]:
			indexs.append(i)
	swapped = [0 for i in range(n)]
	for x in indexs:
		if x == n - 1 and swapped[x] == 0:
			(ref[x - 1], ref[x]) = (ref[x], ref[x - 1])
			break
		if swapped[x] == 0:
			(ref[x], ref[x + 1]) = (ref[x + 1], ref[x])
			swapped[x] = 1
			swapped[x + 1] = 1
	for (i, x) in enumerate(ref):
		if i == n - 1:
			print(x)
			break
		print(x, end=' ')


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		return [-1]
	ans = [i for i in range(1, n + 1)]
	for i in range(n - 1):
		if arr[i] == ans[i]:
			(ans[i], ans[i + 1]) = (ans[i + 1], ans[i])
	if ans[-1] == arr[-1]:
		(ans[-1], ans[-2]) = (ans[-2], ans[-1])
	return ans
for _ in range(int(input())):
	print(*solve())


tc = int(input())
for t in range(tc):
	n = int(input())
	lst = list(map(int, input().split()))
	if n == 1:
		print(-1)
		continue
	arr = [i for i in range(1, n + 1)]
	for i in range(n):
		if i < n - 1 and arr[i] == lst[i]:
			k = arr[i]
			arr[i] = arr[i + 1]
			arr[i + 1] = k
		elif arr[i] == lst[i]:
			k = arr[i]
			arr[i] = arr[i - 1]
			arr[i - 1] = k
	print(' '.join(map(str, arr)))


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	lst1 = []
	if n == 1:
		print(-1)
		continue
	for i in range(1, n + 1):
		lst1.append(i)
	for i in range(n - 1):
		if lst[i] == lst1[i]:
			(lst1[i], lst1[i + 1]) = (lst1[i + 1], lst1[i])
	if lst[-1] == lst1[-1]:
		(lst1[-1], lst1[-2]) = (lst1[-2], lst1[-1])
	print(*lst1)


for i in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	y = sorted(x)
	for i in range(n):
		if y[i] == x[i] and i != n - 1:
			(y[i], y[i + 1]) = (y[i + 1], y[i])
		elif y[i] == x[i] and i == n - 1:
			(y[i], y[i - 1]) = (y[i - 1], y[i])
	if n != 1:
		for i in y:
			print(i, end=' ')
		print()
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l2 = sorted(l)
	if n == 1:
		print(-1)
	else:
		for i in range(n):
			if l2[i] == l[i]:
				if i == n - 1:
					(l2[i], l2[i - 1]) = (l2[i - 1], l2[i])
				else:
					(l2[i], l2[i + 1]) = (l2[i + 1], l2[i])
		print(*l2)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	if len(a) == 1:
		print(-1)
		continue
	b = [0] * n
	for i in range(n):
		b[i] = i + 1
	for i in range(n):
		if a[i] == b[i]:
			if i == n - 1:
				(b[i], b[i - 1]) = (b[i - 1], b[i])
			else:
				(b[i], b[i + 1]) = (b[i + 1], b[i])
	print(*b)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	s = sorted(a[:])
	for i in range(n):
		if a[i] == s[i]:
			if i != len(s) - 1:
				(s[i], s[i + 1]) = (s[i + 1], s[i])
			else:
				(s[i], s[i - 1]) = (s[i - 1], s[i])
	if n == 1:
		print(-1)
	else:
		print(*s)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	mn = []
	if n == 1:
		print(-1)
	else:
		for i in range(n - 1):
			if b[i] == a[i]:
				(b[i], b[i + 1]) = (b[i + 1], b[i])
		if b[-1] == a[-1]:
			(b[-1], b[-2]) = (b[-2], b[-1])
		print(*b)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = [i for i in range(1, n + 1)]
	if n == 1:
		print(-1)
	else:
		for i in range(n - 1):
			if x[i] == l[i]:
				(x[i], x[i + 1]) = (x[i + 1], x[i])
		if x[n - 1] == l[n - 1]:
			(x[n - 2], x[n - 1]) = (x[n - 1], x[n - 2])
		print(*x)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split(' ')))
	if n == 1:
		print(-1)
		continue
	elif n == 2:
		print(l[1], l[0])
		continue
	else:
		k = l.copy()
		k.sort()
		for i in range(n):
			if k[i] == l[i]:
				if i != n - 1:
					(k[i], k[i + 1]) = (k[i + 1], k[i])
					i += 1
				else:
					(k[i - 1], k[i]) = (k[i], k[i - 1])
		print(*k)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	b = []
	for j in x:
		b.append(j)
	b.sort()
	if n == 1:
		print(-1)
	else:
		for i in range(n):
			if x[i] != b[i]:
				continue
			if i + 1 < n:
				(b[i], b[i + 1]) = (b[i + 1], b[i])
			elif i - 1 > 0:
				(b[i], b[i - 1]) = (b[i - 1], b[i])
		print(*b)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a1 = sorted(a)
	bool = True
	for i in range(n):
		if a[i] != a1[i]:
			continue
		if i + 1 < n:
			(a1[i], a1[i + 1]) = (a1[i + 1], a1[i])
		elif i - 1 > 0:
			(a1[i], a1[i - 1]) = (a1[i - 1], a1[i])
		else:
			bool = False
	if bool == True:
		print(*a1)
	else:
		print(-1)


n = int(input())
for i in range(n):
	k = int(input())
	arr = list(map(int, input().split()))
	if k == 1:
		print('-1')
		continue
	brr = arr.copy()
	brr.sort()
	crr = []
	for j in range(k - 1):
		if arr[j] != brr[j]:
			crr.append(brr[j])
		else:
			temp = brr[j]
			brr[j] = brr[j + 1]
			brr[j + 1] = temp
			crr.append(brr[j])
	if arr[-1] == brr[-1]:
		temp = crr[-1]
		crr.pop()
		crr.append(brr[-1])
		crr.append(temp)
	else:
		crr.append(brr[-1])
	print(' '.join(map(str, crr)))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if len(a) == 1:
		print(-1)
		continue
	b = [x for x in range(1, n + 1)]
	for i in range(n - 1):
		if b[i] == a[i]:
			(b[i], b[i + 1]) = (b[i + 1], b[i])
	if b[-1] == a[-1]:
		(b[-1], b[-2]) = (b[-2], b[-1])
	print(*b)


for it in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	for i in range(n - 1):
		if b[i] == a[i]:
			(b[i], b[i + 1]) = (b[i + 1], b[i])
	if n == 1:
		b = [-1]
	elif b[-1] == a[-1]:
		(b[-1], b[-2]) = (b[-2], b[-1])
	print(*b)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(maxsplit=n - 1)))
	b = sorted(a)
	if n == 1:
		print(-1)
		continue
	for i in range(n - 1):
		if b[i] == a[i]:
			(b[i], b[i + 1]) = (b[i + 1], b[i])
	if b[-1] == a[-1]:
		(b[-1], b[-2]) = (b[-2], b[-1])
	print(*b)


for t in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	b = sorted(a)
	c = []
	i = 0
	j = 0
	if n == 1:
		print(-1)
		continue
	while b:
		if b[j] != a[i]:
			c.append(b.pop(j))
			i += 1
			j = 0
		else:
			j += 1
		if len(b) == 1 and a[-1] == b[-1]:
			tm = c[-1]
			c[-1] = b[0]
			c.append(tm)
			break
	print(*c)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = [i for i in range(1, n + 1)]
	for i in range(n):
		if i == n - 1:
			if l[i] == ans[i]:
				(ans[i], ans[i - 1]) = (ans[i - 1], ans[i])
		elif l[i] == ans[i]:
			(ans[i], ans[i + 1]) = (ans[i + 1], ans[i])
	if ans == l:
		print(-1)
	else:
		print(*ans)


t = int(input())
for _ in range(t):
	n = int(input())
	p = [int(x) for x in input().split()]
	if n == 1:
		print('-1')
	else:
		l = sorted(p)
		for i in range(0, n - 1):
			if l[i] == p[i]:
				a = l[i + 1]
				l[i + 1] = l[i]
				l[i] = a
		if p[-1] == l[-1]:
			a = l[-2]
			l[-2] = l[-1]
			l[-1] = a
		print(*l)


for jj in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	b = sorted(arr)
	if n == 1:
		print(-1)
	else:
		for i in range(n):
			if b[i] == arr[i]:
				if i < n - 1:
					(b[i], b[i + 1]) = (b[i + 1], b[i])
				else:
					(b[i], b[i - 1]) = (b[i - 1], b[i])
		print(*b)


t = int(input())
s = []
for i in range(t):
	n = int(input())
	a = input()
	a = a.split()
	a = [int(x) for x in a]
	b = a.copy()
	c = b.copy()
	b.sort()
	if n < 2:
		print(-1)
		continue
	for j in range(n - 1):
		if b[j] == a[j]:
			(b[j], b[j + 1]) = (b[j + 1], b[j])
	m = -1
	while b[m] == a[m]:
		(b[m], b[m - 1]) = (b[m - 1], b[m])
		m -= 1
	for j in range(n):
		print(b[j], end=' ')
	print()


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p = [j for j in range(1, n + 1)]
	for j in range(n):
		if l[j] == p[j]:
			if j == n - 1:
				(p[j - 1], p[j]) = (p[j], p[j - 1])
			else:
				(p[j], p[j + 1]) = (p[j + 1], p[j])
		else:
			continue
	if n == 1:
		print(-1)
	else:
		for j in range(n):
			print(p[j], end=' ')
		print()


import sys

def mapped_read(cast):
	return map(cast, input().split())

def read_list(cast):
	return list(mapped_read(cast))

def solve():
	(n,) = mapped_read(int)
	a = read_list(int)
	if n == 1:
		print(-1)
		return
	ans = [i for i in range(1, n + 1)]
	for (ind, v) in enumerate(a):
		if v == ans[ind]:
			if ind < n - 1:
				(ans[ind], ans[ind + 1]) = (ans[ind + 1], ans[ind])
			else:
				(ans[ind], ans[ind - 1]) = (ans[ind - 1], ans[ind])
	for i in ans:
		print(i, end=' ')
	print()
sys.setrecursionlimit(100010)
(t,) = mapped_read(int)
for _ in range(t):
	solve()


for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	num1 = []
	for i in range(n):
		num1.append(i + 1)
	for i in range(n):
		if i != n - 1:
			if num[i] == num1[i]:
				temp = num1[i]
				num1[i] = num1[i + 1]
				num1[i + 1] = temp
		elif num[i] == num1[i]:
			temp = num1[n - 1]
			num1[n - 1] = num1[n - 2]
			num1[n - 2] = temp
	for i in range(n):
		if num1[i] == num[i]:
			f = 0
			break
		else:
			f = 1
	if f:
		print(*num1)
	else:
		print(-1)


def mystic(A, n):
	B = sorted(A)
	for i in range(n - 1):
		if A[i] == B[i]:
			temp = B[i + 1]
			B[i + 1] = B[i]
			B[i] = temp
	if A[n - 1] == B[n - 1]:
		temp = B[n - 1]
		B[n - 1] = B[n - 2]
		B[n - 2] = temp
	return B
tests = int(input())
for _ in range(tests):
	n = int(input())
	A = list(map(int, input().split()))
	B = mystic(A, n)
	if len(B) == 1:
		print('-1')
	else:
		for i in range(n):
			print(B[i], end=' ')
		print()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	if n == 1:
		print(-1)
	else:
		for i in range(1, n + 1):
			l.append(i)
		for i in range(len(a)):
			if a[i] == l[i]:
				if i != len(a) - 1:
					(l[i + 1], l[i]) = (l[i], l[i + 1])
		if l[-1] == a[-1]:
			(l[-2], l[-1]) = (l[-1], l[-2])
		print(*l)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [0] * n
	i = 1
	if n == 1:
		print(-1)
		continue
	while i < n + 1:
		if arr[i - 1] == i:
			if i == n:
				(ans[i - 1], ans[i - 2]) = (ans[i - 2], i)
				i += 1
			else:
				ans[i - 1] = i + 1
				ans[i] = i
				i += 2
		else:
			ans[i - 1] = i
			i += 1
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = sorted(l)
	if n == 1:
		print(-1)
		continue
	ans = []
	for i in range(n):
		if l[i] == l1[i]:
			if i == n - 1:
				(l1[i], l1[i - 1]) = (l1[i - 1], l1[i])
			else:
				(l1[i], l1[i + 1]) = (l1[i + 1], l1[i])
	for val in l1:
		print(val, end=' ')
	print()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	if n == 1:
		print(-1)
	elif n == 2:
		print(l[1], l[0])
	else:
		lk = [i for i in range(1, n + 1)]
		lans = []
		for i in range(n - 2):
			if lk[0] != l[i]:
				lans.append(lk[0])
				del lk[0]
			else:
				lans.append(lk[1])
				del lk[1]
		if lk[0] != l[n - 2] and lk[1] != l[n - 1]:
			lans += [lk[0], lk[1]]
		else:
			lans += [lk[1], lk[0]]
		print(*lans)


import sys
import heapq
import bisect
import math
from functools import lru_cache
sys.setrecursionlimit(10 ** 6)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, sys.stdin.readline().split()))
	if n == 1:
		print(-1)
	else:
		temp = arr[:]
		heapq.heapify(temp)
		res = [0] * n
		flag = True
		for i in range(n):
			x = heapq.heappop(temp)
			if arr[i] != x:
				res[i] = x
			elif not temp:
				res[i] = res[i - 1]
				res[i - 1] = x
			else:
				y = heapq.heappop(temp)
				res[i] = y
				heapq.heappush(temp, x)
		print(*res)


import sys
from heapq import heappush, heappop

def rall():
	return [x.strip() for x in sys.stdin.readlines()]

def rl():
	return sys.stdin.readline().strip()

def rl_types(types):
	str_list = [x for x in sys.stdin.readline().strip().split(' ')]
	return [types[i](str_list[i]) for i in range(len(str_list))]

def pr(something=''):
	sys.stdout.write(str(something) + '\n')

def pra(array):
	sys.stdout.write(' '.join([str(x) for x in array]) + '\n')

def solve(array):
	return array
NT = int(rl())
for ti in range(NT):
	n = int(rl())
	array = list(map(int, rl().split(' ')))
	if n == 1:
		pr(-1)
		continue
	avail = []
	for i in range(1, n + 1):
		heappush(avail, i)
	new = []
	for i in range(n):
		low = heappop(avail)
		if low == array[i]:
			if len(avail) == 0:
				p = new[-1]
				new[-1] = low
				new.append(p)
			else:
				new.append(heappop(avail))
				heappush(avail, low)
		else:
			new.append(low)
	pra(new)


for _ in range(int(input())):
	n = int(input())
	given = list(map(int, input().split()))
	ans = [0] * n
	i = 1
	if n > 1:
		while i < n + 1:
			if given[i - 1] == i:
				if i != n:
					ans[i] = i
					ans[i - 1] = i + 1
					i += 2
				else:
					t = ans[i - 2]
					ans[i - 2] = i
					ans[i - 1] = t
					i += 1
			else:
				ans[i - 1] = i
				i += 1
		for i in range(n):
			print(ans[i], end=' ')
		print()
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	sorted_array = sorted(array)
	ans = sorted_array
	for i in range(n):
		nxt = i + 1
		if array[i] == sorted_array[i]:
			if i != n - 1:
				nxt = i + 1
			else:
				nxt = i - 1
			(ans[i], ans[nxt]) = (ans[nxt], ans[i])
	if n == 1:
		print(-1)
	else:
		print(' '.join([str(i) for i in ans]))


import sys

def read_line():
	return sys.stdin.readline()

def solve():
	cases = int(read_line())
	for _ in range(cases):
		N = int(read_line())
		arr = read_line().split()
		if N == 1:
			print('-1\n')
			continue
		num_arr = list(map(int, arr))
		num_arr2 = num_arr.copy()
		num_arr2 = sorted(num_arr2)
		for idx in range(len(num_arr2)):
			if num_arr2[idx] == num_arr[idx]:
				if idx == len(num_arr2) - 1:
					(num_arr2[idx], num_arr2[idx - 1]) = (num_arr2[idx - 1], num_arr2[idx])
				else:
					(num_arr2[idx], num_arr2[idx + 1]) = (num_arr2[idx + 1], num_arr2[idx])
		for (idx, item) in enumerate(num_arr2):
			if idx > 0:
				print(' ', end='')
			print(item, end='')
		print('')
solve()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(-1)
	else:
		s = a[:]
		s.sort(reverse=True)
		b = []
		for j in range(n):
			if s[-1] != a[j]:
				b.append(s[-1])
				s.pop()
			elif len(s) == 1:
				b.append(s[0])
				s.pop()
			else:
				b.append(s[-2])
				s.remove(s[-2])
		if b[-1] == a[-1]:
			(b[-1], b[-2]) = (b[-2], b[-1])
		print(*b)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(-1)
	else:
		b = list(range(1, n + 1))
		for x in range(n - 1):
			if a[x] != b[x]:
				continue
			else:
				temp = b[x + 1]
				b[x + 1] = b[x]
				b[x] = temp
		if b[n - 1] == a[n - 1]:
			temp = b[n - 2]
			b[n - 2] = b[n - 1]
			b[n - 1] = temp
		print(' '.join(map(str, b)))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = [i for i in range(1, n + 1)]
	if n == 1:
		print(-1)
		continue
	for i in range(n - 1):
		if ans[i] == a[i]:
			(ans[i], ans[i + 1]) = (ans[i + 1], ans[i])
	if ans[-1] == a[-1]:
		(ans[n - 1], ans[n - 2]) = (ans[n - 2], ans[n - 1])
	for i in range(n):
		print(ans[i], end=' ')
	print()


t = int(input())
for i in range(t):
	m = []
	n = int(input())
	x = input()
	s = x.split(' ')
	for i in range(n):
		s[i] = int(s[i])
	k = sorted(s)
	for i in range(n):
		if k[i] == s[i]:
			if i != n - 1:
				k[i] = k[i + 1]
				k[i + 1] = s[i]
			if i == n - 1:
				w = k[i]
				k[i] = k[i - 1]
				k[i - 1] = w
	for i in range(n):
		m.append(str(k[i]))
	if k == s:
		m = []
		m.append('-1')
	print(' '.join(m))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [i for i in range(1, n + 1)]
	c = []
	for i in a:
		for j in b:
			if j != i:
				c += [j]
				b.remove(j)
				break
			elif j == i and len(b) == 1:
				c += [j]
				x = -1
				while True:
					if x == -1 * n:
						c = [-1]
						break
					for k in range(n):
						if a[k] == c[k]:
							break
					else:
						break
					(c[x], c[x - 1]) = (c[x - 1], c[x])
					x -= 1
	print(*c)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sorted(l)
	for i in range(len(l) - 1):
		if l[i] == s[i]:
			(s[i], s[i + 1]) = (s[i + 1], s[i])
	if l[n - 1] == s[n - 1]:
		(s[n - 1], s[n - 2]) = (s[n - 2], s[n - 1])
	if n == 1:
		print(-1)
	else:
		e = ' '.join(map(str, s))
		print(e)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = [] + l
	x.sort(reverse=True)
	res = []
	if n == 1:
		print(-1)
	else:
		for i in range(n):
			if i == n - 1 and x[-1] == l[i]:
				a = res[-1]
				res.pop()
				res.append(x[-1])
				res.append(a)
				break
			if x[-1] == l[i]:
				a = x[-1]
				x.pop()
				res.append(x[-1])
				x.pop()
				x.append(a)
			else:
				res.append(x[-1])
				x.pop()
		for i in res:
			print(i, end=' ')
		print()


t = int(input())
while t:
	n = int(input())
	a = [int(x) for x in input().split()]
	if n == 1:
		print(-1)
		t -= 1
		continue
	b = []
	c = a.copy()
	c.sort()
	for i in range(n - 2):
		if a[i] != c[0]:
			b.append(c.pop(0))
		else:
			b.append(c.pop(1))
	if c[0] != a[n - 2]:
		if c[1] != a[n - 1]:
			b.append(c.pop(0))
			b.append(c.pop(0))
		else:
			b.append(c.pop(1))
			b.append(c.pop(0))
	else:
		b.append(c.pop(1))
		b.append(c.pop(0))
	print(*b)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	perm = [i for i in input().split(' ')]
	if n == 1:
		print(-1)
		continue
	new_perm = [str(i) for i in range(1, n + 1)]
	for i in range(n):
		if new_perm[i] != perm[i]:
			continue
		elif i != n - 1:
			(new_perm[i], new_perm[i + 1]) = (new_perm[i + 1], new_perm[i])
		else:
			(new_perm[i], new_perm[i - 1]) = (new_perm[i - 1], new_perm[i])
	print(' '.join(new_perm))


def answer(n, lt):
	if n == 1:
		print('-1')
		return -1
	new = lt[:]
	new.sort()
	for i in range(n - 1):
		if new[i] == lt[i]:
			(new[i], new[i + 1]) = (new[i + 1], new[i])
	for i in range(n - 1, -1, -1):
		if new[i] == lt[i]:
			(new[i], new[i - 1]) = (new[i - 1], new[i])
		else:
			break
	ans = ''
	for ele in new:
		ans += str(ele) + ' '
	print(ans)
t = int(input())
for test in range(t):
	n = int(input())
	txt = input()
	lt = list(map(int, txt.split(' ')))
	answer(n, lt)


def solve():
	n = int(input())
	a = list(map(int, input().split(' ')))
	if n == 1:
		print('-1')
		return
	b = a.copy()
	a.sort()
	i = 0
	while i < n - 1:
		if a[i] == b[i]:
			temp = a[i]
			a[i] = a[i + 1]
			a[i + 1] = temp
			i += 2
			continue
		i += 1
	if a[n - 1] == b[n - 1]:
		temp = a[n - 2]
		a[n - 2] = a[n - 1]
		a[n - 1] = temp
	for ele in a:
		print(ele, end=' ')
	print()
t = int(input())
for i in range(t):
	solve()


t = int(input())
ans = []
for x in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	if n == 1:
		ans.append(-1)
		continue
	q = p[:]
	q.sort()
	for x in range(n):
		if q[x] == p[x]:
			if x == n - 1:
				t = q[x]
				q[x] = q[x - 1]
				q[x - 1] = t
			else:
				t = q[x]
				q[x] = q[x + 1]
				q[x + 1] = t
	ans.append(q)
for a in ans:
	if a == -1:
		print(a)
		continue
	for nums in a:
		print(nums, end=' ')
	print()


T = int(input())
for t in range(T):
	n = int(input())
	s = list(map(int, input().split()))
	result = []
	ss = sorted(s)
	for x in s:
		for y in ss:
			if x != y:
				if len(ss) == 2 and y != s[-1] and (y == ss[0]) and (ss[-1] == s[-1]):
					pass
				else:
					result.append(y)
					ss.pop(ss.index(y))
					break
	print(' '.join([str(x) for x in result]) if len(result) == n else -1)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	p = sorted(l)
	if n == 1:
		print(-1)
	else:
		for i in range(n - 1):
			if l[i] == p[i]:
				(p[i], p[i + 1]) = (p[i + 1], p[i])
		if p[-1] == l[-1]:
			(p[-2], p[-1]) = (p[-1], p[-2])
		print(*p)
	t -= 1


t = int(input())
for q in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = sorted(a)
	if n != 1:
		for i in range(0, n - 1):
			if a[i] == b[i]:
				tmp = b[i]
				b[i] = b[i + 1]
				b[i + 1] = tmp
		if a[n - 1] == b[n - 1]:
			tmp = b[n - 1]
			b[n - 1] = b[i]
			b[i] = tmp
		print(*b)
	else:
		print('-1')


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	p_sorted = sorted(p)
	ans = []
	if n == 1:
		print(-1)
		continue
	for i in range(n):
		for j in range(len(p_sorted)):
			if p_sorted[j] != p[i]:
				ans.append(p_sorted[j])
				p_sorted.pop(j)
				break
	if len(ans) != n:
		ans.append(p_sorted[0])
		t = ans[-1]
		ans[-1] = ans[-2]
		ans[-2] = t
	print(*ans)


def solution():
	n = int(input())
	a = list(map(int, input().split()))
	if n <= 1:
		print(-1)
		return
	d = {i: j for (i, j) in enumerate(a)}
	used = {i: False for i in a}
	a.sort()
	for i in range(n - 1):
		if a[i] == d[i]:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
	if a[n - 1] == d[n - 1]:
		(a[n - 1], a[n - 2]) = (a[n - 2], a[n - 1])
	print(*a)
try:
	import sys
	import os
	if os.path.exists('.cpl_files/2.in.txt'):
		sys.stdin = open('.cpl_files/2.in.txt', 'r')
		sys.stdout = open('.cpl_files/2.out.txt', 'w')
except:
	pass
t = int(input())
while t:
	solution()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	q = p.copy()
	p.sort(reverse=True)
	t = []
	for i in range(n):
		if p[-1] != q[i]:
			t.append(p[-1])
			p.pop()
		else:
			try:
				t.append(p[-2])
				p.pop(-2)
			except:
				t.insert(-1, p[-1])
	if t == q:
		print(-1)
	else:
		print(' '.join(map(str, t)))


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(-1)
		return
	ans = []
	i = 1
	s = set()
	flag = False
	for j in range(n - 1):
		if not flag:
			if arr[j] != i:
				ans.append(i)
				s.add(i)
				i += 1
			else:
				ans.append(i + 1)
				s.add(i + 1)
				flag = True
		else:
			ans.append(i)
			s.add(i)
			i += 2
			flag = False
	if n not in s:
		ans.append(n)
		if arr[-1] == n:
			(ans[-1], ans[-2]) = (ans[-2], ans[-1])
	else:
		ans.append(n - 1)
	for z in ans:
		print(z, end=' ')
	print()
	return
	return ans
for _ in range(int(input())):
	main()


t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[:]
	b.sort()
	c = []
	if n == 1:
		print(-1)
	else:
		for i in range(n):
			if b[i] != a[i]:
				c.append(b[i])
			elif i < n - 1:
				(b[i], b[i + 1]) = (b[i + 1], b[i])
				c.append(b[i])
			else:
				c.append(b[i])
		if a[n - 1] == b[n - 1]:
			(c[n - 1], c[n - 2]) = (c[n - 2], c[n - 1])
		print(*c)


for _ in range(int(input())):
	n = int(input())
	lis = [int(i) for i in input().split()]
	if len(lis) == 1:
		print(-1)
	else:
		new_lis = list(range(1, n + 1))
		for i in range(n - 1):
			if new_lis[i] == lis[i]:
				(new_lis[i], new_lis[i + 1]) = (new_lis[i + 1], new_lis[i])
		if new_lis[-1] == lis[-1]:
			(new_lis[-2], new_lis[-1]) = (new_lis[-1], new_lis[-2])
		print(*new_lis, sep=' ')


testcases = int(input())
for j in range(testcases):
	n = int(input())
	l = [int(x) for x in input().split(' ')]
	if n == 1:
		print(-1)
		continue
	res = [i + 1 for i in range(n)]
	i = 0
	while i < n - 1:
		if l[i] == i + 1:
			(res[i], res[i + 1]) = (res[i + 1], res[i])
			i += 2
		else:
			i += 1
	if res[n - 1] == n and l[n - 1] == n:
		(res[n - 1], res[n - 2]) = (res[n - 2], res[n - 1])
	for i in range(n):
		print(res[i], end=' ')
	print()


import copy

def sol(n, p):
	if n <= 1:
		return -1
	q = copy.deepcopy(p)
	q.sort()
	res = []
	skip = False
	for i in range(len(p)):
		if q[i] is None and (not skip):
			continue
		if skip:
			res.append(q[i - 1])
			q[i - 1] = None
			skip = False
			continue
		if q[i] == p[i]:
			if i == len(p) - 1:
				res.append(q[i])
				(res[i], res[i - 1]) = (res[i - 1], res[i])
			else:
				skip = True
				res.append(q[i + 1])
				q[i + 1] = None
			continue
		else:
			res.append(q[i])
			q[i] = None
	return ' '.join(list(map(lambda x: str(x), res)))
test_cases = int(input().strip())
for t in range(test_cases):
	n = int(input().strip())
	p = list(map(lambda x: int(x), input().strip().split(' ')))
	print(sol(n, p))


for j in range(int(input())):
	c = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	for i in range(c - 1):
		if b[i] == a[i]:
			t = b[i + 1]
			b[i + 1] = b[i]
			b[i] = t
	if c != 1 and b[c - 1] == a[c - 1]:
		t = b[c - 1]
		b[c - 1] = b[c - 2]
		b[c - 2] = t
	if c != 1:
		print(*b)
	else:
		print(-1)


def merge(Left, Right):
	sortedArray = []
	L = len(Left)
	R = len(Right)
	l = 0
	r = 0
	i = 0
	while l + r < L + R:
		if r >= R or (l < L and Left[l] < Right[r]):
			sortedArray.append(Left[l])
			l += 1
		else:
			sortedArray.append(Right[r])
			r += 1
	return sortedArray

def mergeSort(arr):
	n = len(arr)
	if n == 1:
		return arr
	Left = mergeSort(arr[:n // 2])
	Right = mergeSort(arr[n // 2:])
	return merge(Left, Right)

def swapper(arr, j):
	temp = arr[j]
	if j == len(arr) - 1:
		temp = arr[j]
		arr[j] = arr[j - 1]
		arr[j - 1] = temp
	else:
		arr[j] = arr[j + 1]
		arr[j + 1] = temp
	return arr
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(j) for j in input().split()]
	if n == 1:
		print(-1)
		continue
	arrSorted = mergeSort(arr)
	finArr = []
	j = 0
	while j < n:
		if arr[j] != arrSorted[j]:
			j += 1
		else:
			arrSorted = swapper(arrSorted, j)
	print(' '.join([str(j) for j in arrSorted]))


import math
t = int(input())
while t:
	t -= 1
	h = input()
	a = int(h)
	lis = input().split()
	lis = [int(x) for x in lis]
	best = list(range(1, a + 1))
	for i in range(0, a - 1):
		if lis[i] != best[0]:
			lis[i] = best.pop(0)
		else:
			lis[i] = best.pop(1)
	if lis[a - 1] != best[0]:
		lis[a - 1] = best[0]
	else:
		lis[a - 1] = lis[a - 2]
		lis[a - 2] = best[0]
	if a == 1:
		print(-1)
	else:
		lis = [str(x) for x in lis]
		print(' '.join(lis))


def check():
	return

def exe():
	l = p.copy()
	l.sort()
	ans = []
	pointer = 0
	for i in range(n):
		if l[0] != p[i]:
			ans.append(l[0])
			l.remove(l[0])
		else:
			for j in range(len(l)):
				if l[j] != p[i]:
					ans.append(l[j])
					l.remove(l[j])
					break
	if ans == []:
		print(-1)
		return
	if len(ans) != n:
		ans.append(l[0])
		if ans[-1] == l[-1]:
			temp = ans[-2]
			ans[-2] = ans[-1]
			ans[-1] = temp
	print(*ans)
for i in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	exe()


def solution(arr, length):
	if length == 0 or length == 1:
		return -1
	sorted_arr = sorted(arr)
	for i in range(length):
		if i == length - 1:
			if sorted_arr[i] == arr[i]:
				(sorted_arr[i], sorted_arr[i - 1]) = (sorted_arr[i - 1], sorted_arr[i])
		if sorted_arr[i] == arr[i]:
			(sorted_arr[i], sorted_arr[i + 1]) = (sorted_arr[i + 1], sorted_arr[i])
	return sorted_arr
n = int(input())
for i in range(n):
	length = int(input())
	arr = list(map(int, input().split()))
	res = solution(arr, length)
	if isinstance(res, list):
		print(*res, sep=' ')
	else:
		print(res)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a.copy()
	b.sort()
	if n == 1:
		print(-1)
	else:
		for i in range(0, n):
			if b[i] == a[i]:
				if i == n - 1:
					(b[i], b[i - 1]) = (b[i - 1], b[i])
				else:
					(b[i], b[i + 1]) = (b[i + 1], b[i])
		for i in b:
			print(i, end=' ')
		print()


t = int(input())
for i in range(t):
	N = int(input())
	l = [int(i) for i in input().split()]
	if N == 1:
		print(-1)
		continue
	l_sort = l.copy()
	l_sort.sort()
	out = []
	for elm in l:
		i = 0
		while l_sort[i] == elm and i < len(l_sort) - 1:
			i += 1
		out.append(l_sort[i])
		l_sort.pop(i)
	if out[len(out) - 1] == l[len(out) - 1]:
		i = len(out) - 1
		while out[len(out) - 1] == l[i] and i >= 0:
			i -= 1
		a = out[len(out) - 1]
		out[len(out) - 1] = out[i]
		out[i] = a
	for elm in out:
		print(elm, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	c = sorted(p)
	if n == 1:
		print(-1)
		continue
	for i in range(n):
		if p[i] != c[i]:
			continue
		if i == n - 1:
			(c[n - 1], c[n - 2]) = (c[n - 2], c[n - 1])
		else:
			(c[i], c[i + 1]) = (c[i + 1], c[i])
	print(*c)


t = int(input())
for _ in range(t):
	(n,) = map(int, input().split())
	a = list(map(int, input().split()))
	b = sorted(a)
	x = []
	for i in range(n):
		if a[i] == b[i]:
			x.append(i)
	s = set(x)
	if n == 1:
		print(-1)
		continue
	for i in range(n):
		if i in s:
			if i < n - 1:
				(b[i], b[i + 1]) = (b[i + 1], b[i])
				if i + 1 in s:
					s.remove(i + 1)
				s.remove(i)
			else:
				(b[i], b[i - 1]) = (b[i - 1], b[i])
				if i - 1 in s:
					s.remove(i - 1)
				s.remove(i)
	print(*b)


t = int(input())
for T in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	hm = [[0 for ii in range(2)] for jj in range(n)]
	for i in range(n):
		hm[i][0] = a[i]
		hm[i][1] = i
	hm.sort()
	b = [0] * n
	if n == 1:
		print(-1)
	else:
		i = 0
		while i < n:
			if hm[i][0] == a[i]:
				if i == n - 1:
					u = b[i - 1]
					b[i - 1] = hm[i][0]
					b[i] = u
				else:
					b[i] = hm[i + 1][0]
					b[i + 1] = hm[i][0]
				i += 1
			else:
				b[i] = hm[i][0]
			i += 1
		print(*b)


n = int(input())
for i in range(n):
	a = int(input())
	b = [int(j) for j in input().split()]
	c = sorted(b)
	for j in range(a):
		if c[j] == b[j]:
			if j + 1 < a:
				(c[j], c[j + 1]) = (c[j + 1], c[j])
			else:
				(c[j], c[j - 1]) = (c[j - 1], c[j])
	if c == b:
		print(-1)
	else:
		print(*c)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	if len(b) == 1:
		print(-1)
		continue
	for i in range(len(a)):
		if a[i] == b[i]:
			if i == n - 1:
				(b[-1], b[-2]) = (b[-2], b[-1])
			else:
				(b[i], b[i + 1]) = (b[i + 1], b[i])
	print(*b)


def printer(l, srt):
	print(*l)
	print(*srt)
	print()

def solution(n, l, srt):
	if n == 1:
		return [-1]
	for i in range(n - 1):
		if srt[i] != l[i]:
			continue
		else:
			(srt[i], srt[i + 1]) = (srt[i + 1], srt[i])
	if srt[-1] == l[-1]:
		(srt[n - 1], srt[n - 2]) = (srt[n - 2], srt[n - 1])
	return srt
tc = int(input())
for i in range(tc):
	n = int(input())
	l = list(map(int, input().split()))
	srt = l[::-1]
	srt.sort()
	ANS = solution(n, l, srt)
	print(*ANS)


for _ in range(int(input())):
	n = int(input())
	old = [int(a) for a in input().split()]
	arr = sorted(old)
	i = 0
	while i < n - 1:
		if old[i] == arr[i]:
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		i += 1
	if old[i] == arr[i]:
		if i == 0:
			print(-1)
		else:
			(arr[i - 1], arr[i]) = (arr[i], arr[i - 1])
			print(' '.join(map(str, arr)))
	else:
		print(' '.join(map(str, arr)))


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	new_arr = [] + arr
	new_arr.sort()
	new_arr.sort()
	if n == 1:
		ans = -1
	else:
		ans = []
		length = 0
		while len(ans) != n:
			if len(new_arr) == 2 and arr[n - 1] == new_arr[1]:
				ans.append(new_arr[1])
				length += 1
				new_arr = new_arr[0:1]
			elif arr[length] != new_arr[0]:
				ans.append(new_arr[0])
				length += 1
				new_arr = new_arr[1:]
			else:
				ans.append(new_arr[1])
				new_arr = new_arr[0:1] + new_arr[2:]
				length += 1
	if ans == -1:
		print(-1)
	else:
		for j in range(n):
			if j != n - 1:
				print(ans[j], end=' ')
			else:
				print(ans[j])


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if n == 1:
		print(-1)
	else:
		lst = []
		for i in range(1, n + 1):
			lst.append(i)
		for i in range(n - 1):
			if l[i] == lst[i]:
				(lst[i], lst[i + 1]) = (lst[i + 1], lst[i])
			else:
				pass
		if l[n - 1] == lst[n - 1]:
			(lst[n - 1], lst[n - 2]) = (lst[n - 2], lst[n - 1])
		for i in lst:
			print(i, end=' ')
		print()


t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	res = sorted(p)
	shift = False
	for i in range(n - 1):
		if res[i] == p[i]:
			(res[i], res[i + 1]) = (res[i + 1], res[i])
	if n > 1:
		if res[n - 1] == p[n - 1]:
			(res[n - 1], res[n - 2]) = (res[n - 2], res[n - 1])
	if n > 1:
		print(' '.join(map(str, res)))
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	crr = arr.copy()
	x = sorted(arr)
	z = 100000
	for i in range(n):
		if x[i] != arr[i]:
			arr[i] = x[i]
			z = 100000
		else:
			z = min(z, i)
			if i != n - 1:
				arr[i] = x[i + 1]
				x[i + 1] = x[i]
			elif arr[i] != crr[z]:
				arr[i] = crr[z]
			else:
				(arr[i], arr[i - 1]) = (arr[i - 1], arr[i])
	if crr == arr:
		print(-1)
	else:
		print(*arr)


import math
from collections import defaultdict
mod = 2 * 10 ** 5

def sol():
	n = int(input())
	a = list(map(int, input().split()))
	b = a[:]
	c = []
	if n == 1:
		print(-1)
		return
	b.sort()
	cntA = 0
	for i in range(n):
		if b[i] != a[i]:
			c.append(b[i])
		elif i == n - 1:
			r = c.pop()
			c.append(b[n - 1])
			c.append(r)
		else:
			c.append(b[i + 1])
			b[i + 1] = b[i]
	print(*c)

def main():
	for _ in range(int(input())):
		sol()
main()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(-1)
		continue
	samp = [i for i in range(1, n + 1)]
	for i in range(0, n - 1):
		if a[i] == samp[i]:
			(samp[i], samp[i + 1]) = (samp[i + 1], samp[i])
	if a[n - 1] == samp[n - 1]:
		(samp[n - 1], samp[n - 2]) = (samp[n - 2], samp[n - 1])
	print(*samp)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l2 = l1.copy()
	if n == 1:
		print(-1)
	if n > 1:
		l2.sort()
		for i in range(n - 1):
			if l1[i] == l2[i]:
				(l2[i % n], l2[(i + 1) % n]) = (l2[(i + 1) % n], l2[i % n])
		if l1[n - 1] == l2[n - 1]:
			(l2[n - 1], l2[n - 2]) = (l2[n - 2], l2[n - 1])
		print(*l2)


t = int(input())
for _ in range(t):
	input()
	p = list(map(lambda x: int(x), input().split()))
	if len(p) == 1:
		print(-1)
		continue
	remaining = sorted(p)
	cur = []
	while len(remaining) > 2:
		if remaining[0] == p[len(cur)]:
			cur.append(remaining.pop(1))
		else:
			cur.append(remaining.pop(0))
	if p[-1] == remaining[1] or p[-2] == remaining[0]:
		cur.append(remaining[1])
		cur.append(remaining[0])
	else:
		cur.append(remaining[0])
		cur.append(remaining[1])
	print(' '.join(map(lambda x: str(x), cur)))


def mystic_permutation(a, n):
	if n == 1:
		print(-1)
		return
	a1 = list(range(1, n + 1))
	for ix in range(n - 1):
		if a[ix] == a1[ix]:
			(a1[ix], a1[ix + 1]) = (a1[ix + 1], a1[ix])
	if a1[n - 1] == a[n - 1]:
		(a1[n - 2], a1[n - 1]) = (a1[n - 1], a1[n - 2])
	print(' '.join(map(str, a1)))
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	mystic_permutation(a, n)


tc = int(input())
while tc > 0:
	n = int(input())
	A = [int(i) for i in input().split(' ')]
	B = []
	for i in range(n):
		B = B + [[A[i], i]]
	B.sort()
	flag = 0
	if n == 1:
		print('-1')
		flag = 1
	else:
		i = 0
		while i < n:
			if i == B[i][1] and i + 1 < n:
				temp = B[i][0]
				B[i][0] = B[i + 1][0]
				B[i + 1][0] = temp
				i = i + 2
			elif i == B[i][1] and i + 1 >= n:
				temp = B[i][0]
				B[i][0] = B[i - 1][0]
				B[i - 1][0] = temp
				i = i + 2
			else:
				i = i + 1
	for i in range(n):
		A[i] = str(B[i][0])
	if flag == 0:
		print(' '.join(A))
	tc = tc - 1


strng = lambda : input()
inp = lambda : int(input())
mul = lambda : map(int, input().split())
jn = lambda x, l: x.join(map(str, l))
strlst = lambda : list(input())
lst = lambda : list(map(int, input().split()))
dd = lambda : defaultdict(lambda : 0)
from collections import defaultdict
from math import ceil, log, floor, sqrt, gcd, log10
for _ in range(inp()):
	n = inp()
	l1 = lst()
	d = dd()
	for i in range(n):
		d[l1[i]] += 1
	l2 = l1.copy()
	l2.sort()
	if n == 1:
		print(-1)
		continue
	for i in range(n):
		if l1[i] == l2[i]:
			break
	else:
		print(jn(' ', l2))
		continue
	for i in range(n - 1):
		if l1[i] == l2[i]:
			tmp = l2[i]
			l2[i] = l2[i + 1]
			l2[i + 1] = tmp
	if l1[n - 1] == l2[n - 1]:
		tmp = l2[n - 1]
		l2[n - 1] = l2[n - 2]
		l2[n - 2] = tmp
	print(jn(' ', l2))


t = int(input())
while t > 0:
	n = int(input())
	a = [int(x) for x in input().split()]
	b = sorted(a)
	if len(a) < 2:
		print(-1)
	else:
		i = 0
		list_final = False
		while not list_final:
			list_final = True
			while i < len(a):
				if a[i] == b[i]:
					list_final = False
					if i != len(a) - 1:
						(b[i], b[i + 1]) = (b[i + 1], b[i])
					else:
						(b[i], b[i - 1]) = (b[i - 1], b[i])
				i += 1
		print(' '.join([str(p) for p in b]))
	t -= 1