Chef has a cubic die with 6 faces kept on an infinite plane. Each face has a distinct integer in the range [1,6] written on it, but the exact arrangement of the numbers on the faces of the die is unknown to Chef. Curiosity gets the better of Chef and he wants to find out o(1), o(2), ..., o(6), where o(i) is the number written opposite to the number i.

	Chef performs the following N-1 steps to learn the exact arrangement of the numbers on the die. In the i-th step, Chef pushes the die in some direction (there are 4 possible directions), and the die rolls 90o in this direction. The picture below demonstrates a die and the result that it produced after rolling in each of the 4 directions respectively. For this die, we have o(1)=4, o(2)=5, o(3)=6, o(4)=1, o(5)=2, o(6)=3.

	Chef records N numbers A1, A2, ..., AN, where Ai is the number written on the top of the die before the i-th step. However, the information on the direction in which he pushes the die each time are lost. Can you help him determine the arrangement of 1-6? You need to output o(1), o(2), ..., o(6). If there are multiple solutions, output any one of them.

-----
	Input-----
- The first line of input contains a single integer T, the number of test cases.
- Each test case consists of two lines.
- The first line contains an integer N, and the second line contains N space-separated integers A1, A2, ..., AN.

-----
	Output-----

	For each test case, output one line. If a possible solution exists, then output 6 space-separated integers o(1), o(2), ..., o(6); otherwise, output -1.

-----
	Constraints-----

- 1 ≤ T, N ≤ 500
- 1 ≤ Ai ≤ 6

	Subtask #1 (17 points):

- N ≤ 2

	Subtask #2 (83 points):

- original constraints

-----
	Example-----
Input:
4
9
1 3 4 6 1 3 4 6 1
10
1 2 1 3 1 4 1 5 1 6
6
1 2 3 4 5 6
4
1 3 3 1

Output:
2 1 6 5 4 3
-1
4 5 6 1 2 3
-1

-----
	Explanation-----
Example case 1: See below.

Example case 2: You can prove that there's no solution.
Example case 3: The solution is not unique. 3 5 1 6 2 4 is another valid solution.

Difficulty: HARD
Tags: Complete search

Constructive algorithms

Ad-hoc
Skill types: Complete search

Starter code:

Solutions:
ori = [[2, 1, 4, 3, 6, 5], [2, 1, 5, 6, 3, 4], [2, 1, 6, 5, 4, 3], [3, 4, 1, 2, 6, 5], [3, 5, 1, 6, 2, 4], [3, 6, 1, 5, 4, 2], [4, 3, 2, 1, 6, 5], [4, 5, 6, 1, 2, 3], [4, 6, 5, 1, 3, 2], [5, 3, 2, 6, 1, 4], [5, 4, 6, 2, 1, 3], [5, 6, 4, 3, 1, 2], [6, 3, 2, 5, 4, 1], [6, 4, 5, 2, 3, 1], [6, 5, 4, 3, 2, 1]]
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	d = [[] for i in range(7)]
	lol = False
	for i in range(1, n):
		if a[i] == a[i - 1]:
			print('-1')
			lol = True
			break
		d[a[i - 1]].append(a[i])
		d[a[i]].append(a[i - 1])
	if lol:
		continue
	for x in ori:
		for i in range(1, 6):
			if d[i].count(x[i - 1]) > 0:
				break
		else:
			print(*x)
			break
	else:
		print('-1')


from itertools import permutations

def solve(n, a):
	ans = []
	for des in desire:
		check = 1
		for i in range(n - 1):
			if a[i] == a[i + 1]:
				return [-1]
			if a[i + 1] == des[a[i] - 1]:
				check = 0
				break
		if check:
			ans = des
			break
	if ans:
		return ans
	return [-1]
per = permutations([1, 2, 3, 4, 5, 6])
desire = []
for p in per:
	check = 1
	for i in range(1, 7):
		if p[i - 1] == i:
			check = 0
			break
	if check:
		doublecheck = 1
		for i in range(6):
			if p[p[i] - 1] != i + 1:
				doublecheck = 0
				break
		if doublecheck:
			desire.append(p)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(*solve(n, a))


def backtrack(k, A, ans):
	if k == 7:
		return True
	if ans[k] != -1:
		return backtrack(k + 1, A, ans)
	for i in range(1, 7):
		if A[k][i] and ans[k] == -1 and (ans[i] == -1):
			ans[k] = i
			ans[i] = k
			solved = backtrack(k + 1, A, ans)
			if solved:
				return True
			else:
				ans[k] = -1
				ans[i] = -1
	return False

def solution():
	n = int(input())
	P = [[True for x in range(7)] for x in range(7)]
	for i in range(1, 7):
		P[i][i] = False
	A = list(map(int, input().split()))
	no_solution = False
	last_num = A[0]
	for i in range(1, n):
		num = A[i]
		if last_num == num:
			no_solution = True
		P[last_num][num] = False
		P[num][last_num] = False
		last_num = num
	if no_solution:
		print(-1)
		return
	ans = [-1 for x in range(7)]
	if backtrack(1, P, ans):
		print(' '.join(map(str, ans[1:])))
	else:
		print(-1)
T = int(input())
while T > 0:
	T = T - 1
	solution()


T = int(input())

def findSolution(currentSolution, adj):
	if len(currentSolution) == 6:
		return currentSolution
	for i in range(1, 7):
		if i in currentSolution:
			continue
		for a in range(1, 7):
			if a not in currentSolution and a != i and (a not in adj[i]):
				copy = dict(currentSolution)
				copy[i] = a
				copy[a] = i
				r = findSolution(copy, adj)
				if r != -1:
					return r
		break
	return -1
for TCN in range(T):
	N = int(input())
	adj = {x: set() for x in range(1, 7)}
	wk = True
	ins = [int(i) for i in input().split()]
	for (a, b) in zip(ins, ins[1:]):
		adj[a].add(b)
		adj[b].add(a)
	for die in range(1, 7):
		if die in adj[die]:
			wk = False
			print(-1)
			break
		if len(adj[die]) > 4:
			wk = False
			print(-1)
			break
	if not wk:
		continue
	sol = findSolution(dict(), adj)
	if sol == -1:
		print(-1)
	else:
		print(' '.join([str(sol[i]) for i in range(1, 7)]))


t = int(input())
di = []
for i in range(15):
	ab = [2, 3, 4, 5, 6]
	te = [0, 0, 0, 0, 0, 0]
	te[0] = i // 3 + 2
	te[i // 3 + 1] = 1
	ab.remove(i // 3 + 2)
	x1 = ab.pop(0)
	te[x1 - 1] = ab[i % 3]
	te[ab[i % 3] - 1] = x1
	ab.pop(i % 3)
	te[ab[0] - 1] = ab[1]
	te[ab[1] - 1] = ab[0]
	di.append(te)
for i in range(t):
	flag = 0
	n = int(input())
	a = list(map(int, input().strip().split()))
	for j in range(15):
		f = 0
		for k in range(n - 1):
			if di[j][a[k] - 1] == a[k + 1] or a[k] == a[k + 1]:
				f = 1
				break
		if f == 1:
			continue
		else:
			for z in di[j]:
				print(z, end=' ')
			print()
			flag = 1
			break
	if flag == 0:
		print(-1)


from itertools import permutations
cases = int(input())

def is_valid(p):
	for index in range(6):
		if index + 1 != p[p[index] - 1] or index + 1 == p[index]:
			return False
	return True

def satisfies(p, opps):
	for index in range(6):
		if p[index] in opps[index]:
			return False
	return True
for _ in range(cases):
	rolls = int(input())
	array = list(map(int, input().split()))
	opps = [set() for k in range(1, 7)]
	if len(array) >= 2:
		opps[array[0] - 1].add(array[1])
		opps[array[-1] - 1].add(array[-2])
	for index in range(1, rolls - 1):
		opps[array[index] - 1].add(array[index - 1])
		opps[array[index] - 1].add(array[index + 1])
	poss = True
	for index in range(6):
		for item in opps[index]:
			if item == index + 1:
				poss = False
				break
		if len(opps[index]) == 5:
			poss = False
			break
	o = False
	for p in permutations((1, 2, 3, 4, 5, 6)):
		if poss and is_valid(p) and satisfies(p, opps):
			o = True
			print(' '.join(list(map(str, p))))
			break
	if not o:
		print(-1)


def dfs(src, vis):
	vis.remove(src)
	for dst in D[src]:
		if dst in vis:
			vis.remove(dst)
			if len(vis) == 0:
				vis.add(src)
				vis.add(dst)
				return (True, [(src, dst)])
			e = vis.pop()
			vis.add(e)
			(val, ret) = dfs(e, vis)
			if val:
				vis.add(src)
				vis.add(dst)
				ret.append((src, dst))
				return (val, ret)
			vis.add(dst)
	vis.add(src)
	return (False, None)
T = int(input().strip())
while T:
	N = int(input().strip())
	B = True
	E = [0] * 7
	A = [int(x) for x in input().strip().split()]
	C = {1, 2, 3, 4, 5, 6}
	D = {1: C - {1}, 2: C - {2}, 3: C - {3}, 4: C - {4}, 5: C - {5}, 6: C - {6}}
	for i in range(1, N):
		if A[i] == A[i - 1]:
			B = False
			break
		if A[i - 1] in D[A[i]]:
			D[A[i]].remove(A[i - 1])
			D[A[i - 1]].remove(A[i])
		if len(D[A[i]]) == 0 or len(D[A[i - 1]]) == 0:
			B = False
			break
	if B:
		(val, vis) = dfs(1, C)
		if val:
			E[vis[0][0]] = vis[0][1]
			E[vis[0][1]] = vis[0][0]
			E[vis[1][0]] = vis[1][1]
			E[vis[1][1]] = vis[1][0]
			E[vis[2][0]] = vis[2][1]
			E[vis[2][1]] = vis[2][0]
			print(E[1], E[2], E[3], E[4], E[5], E[6])
		else:
			print(-1)
	else:
		print(-1)
	T -= 1


def allPairs(n):
	if len(n) == 2:
		return [[tuple(n)]]
	ret = []
	for y in n[1:]:
		ret0 = allPairs([z for z in n[1:] if z != y])
		ret0 = [[(n[0], y)] + z for z in ret0]
		ret += ret0
	return ret
allp = allPairs(list(range(1, 7)))

def getOpposites(a):
	ret = [0] * 6
	for (x, y) in a:
		ret[x - 1] = str(y)
		ret[y - 1] = str(x)
	return ret

def getResult(x):
	aa = allp
	for (i, y) in enumerate(x[:-1]):
		z = x[i + 1]
		q = tuple(sorted([y, z]))
		if y == z:
			return '-1'
		aa = [a for a in aa if q not in a]
		if not aa:
			return '-1'
	return ' '.join(getOpposites(aa[0]))
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	n = int(f.readline())
	x = list(map(int, f.readline().split()))
	print(getResult(x))


def getmintuple(a, b):
	if a > b:
		(a, b) = (b, a)
	return (a, b)

def generatepairs(b):
	p = []
	for j in range(1, 7):
		if j not in sol and j != b:
			if getmintuple(b, j) not in q:
				p.append(j)
	return p

def unusedfromsol():
	for i in range(1, 7):
		if i not in sol:
			return i
tc = int(input())
for case in range(tc):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	q = {}
	solution = 0
	for i in range(1, n):
		a = arr[i - 1]
		b = arr[i]
		(a, b) = getmintuple(a, b)
		if a == b:
			solution = -1
		q[a, b] = True
	if solution == -1:
		print(-1)
		continue
	i = 1
	turns = 0
	sol = [-1] * 7
	sol[0] = False
	nextinp = False
	for turns in range(3):
		a1 = unusedfromsol()
		for blvl1 in generatepairs(a1):
			sol[blvl1] = a1
			sol[a1] = blvl1
			a2 = unusedfromsol()
			for blvl2 in generatepairs(a2):
				sol[blvl2] = a2
				sol[a2] = blvl2
				a3 = unusedfromsol()
				for blvl3 in generatepairs(a3):
					sol[blvl3] = a3
					sol[a3] = blvl3
					if -1 not in sol:
						for k in range(1, 7):
							print(sol[k], end=' ')
						print()
						nextinp = True
						break
				if nextinp:
					break
				sol[blvl2] = -1
				sol[a2] = -1
			if nextinp:
				break
			sol[blvl1] = -1
			sol[a1] = -1
		if nextinp:
			break
	if not nextinp:
		print(-1)


from itertools import permutations
for _ in range(int(input())):
	flag1 = True
	n = int(input())
	a = [int(x) for x in input().split()]
	d = {k: set(range(1, 7)) for k in range(1, 7)}
	for k in range(1, 7):
		d[k].discard(k)
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			flag1 = False
			print(-1)
			break
		d[a[i]].discard(a[i + 1])
		d[a[i + 1]].discard(a[i])
	if flag1:
		flag2 = True
		for p in permutations(range(1, 7)):
			flag3 = True
			for i in range(1, 7):
				b = p[i - 1]
				if p[b - 1] != i or b not in d[i]:
					flag3 = False
					break
			if flag3:
				flag2 = False
				print(*p)
				break
		if flag2:
			print(-1)