An array is called *lovely* if the sum of product of each adjacent pair of elements is odd.

More formally, the array S of size M is lovely if the value \sum_{i=1}^{M-1} (S_{i} . S_{i+1}) is odd.

You are given an array A consisting of N positive integers. Find a [permutation] of array A which is *lovely*. 

If multiple such permutations are possible, output any. If there is no *lovely* permutation, output -1.

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

- The first line contains an integer T denoting the number of test cases. The T test cases then follow.
- The first line of each test case contains an integer N.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N}.

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

For each test case, if a *lovely* permutation of A is possible, print a single line containing N integers denoting the elements of any *lovely* permutation of A. Otherwise, print -1.

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

$1 ≤T ≤1000$
$2 ≤N ≤500$
$1 ≤A_{i} ≤10^{6}$

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

Subtask 1 (100 points): Original constraints.

----- Sample Input 1 ------ 
2
5
1 2 3 4 10
3
7 11 145
----- Sample Output 1 ------ 
3 1 10 2 4
-1
----- explanation 1 ------ 
Test Case $1$: The sum of products of adjacent pair of elements of the given array is $1\cdot 2 + 2\cdot 3 + 3\cdot 4 + 4\cdot 10 = 2+6+12+40 = 60$. Since this value is even, this is not a *lovely* permutation of the array.  
A *lovely* permutation of the given array is $[3, 1, 10, 2, 4]$. The sum of products for this array would be $3\cdot 1 + 1\cdot 10 + 10\cdot 2 + 2\cdot 4 = 41$, which is odd.

Test Case $2$: No permutation of the given array exists where the sum of products of adjacent pair of elements is odd. Thus, answer is $-1$.

Difficulty: MEDIUM
Tags: Constructive algorithms

Starter code:

Solutions:
(k1, k2) = (-1, -1)
k3 = 0
k4 = 100
n = int(input())
while n:
	n -= 1
	b = int(input())
	a = list(map(int, input().split()))
	(p1, p2) = (0, 0)
	for i in a:
		if i & 1:
			p1 += 1
		else:
			p2 += 1
	if p1 == 0 or (p2 == 0 and p1 & 1) or p1 == 1:
		print(-1)
	else:
		(s1, s2) = ([], [])
		for i in a:
			if i & 1:
				s1.append(i)
			else:
				s2.append(i)
		if p1 & 1:
			s2.append(s1.pop())
		for i in s1:
			print(i, end=' ')
		for i in s2:
			print(i, end=' ')
		print()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	odd = []
	even = []
	for i in range(n):
		if a[i] % 2 == 0:
			even.append(a[i])
		else:
			odd.append(a[i])
	spa = len(even)
	if spa == 0:
		if len(odd) % 2 == 0:
			print(*odd)
		else:
			print(-1)
	else:
		ans = []
		if len(odd) == 1 or len(odd) == 0:
			print(-1)
		elif len(odd) % 2 == 0:
			ans = even + odd
			print(*ans)
		else:
			ans = odd[:1] + even + odd[1:]
			print(*ans)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	(odd, eve) = (0, 0)
	for i in a:
		if i & 1:
			odd += 1
		else:
			eve += 1
	if odd == 0 or (eve == 0 and odd & 1) or odd == 1:
		print(-1)
	else:
		(o, e) = ([], [])
		for i in a:
			if i & 1:
				o.append(i)
			else:
				e.append(i)
		if odd & 1:
			e.append(o.pop())
		for i in o:
			print(i, end=' ')
		for i in e:
			print(i, end=' ')
		print()


from itertools import permutations

def solve1():
	n = int(input())
	arr = list(map(int, input().split()))
	odd = []
	i = 0
	while i < len(arr):
		if arr[i] % 2:
			odd.append(arr[i])
			del arr[i]
		else:
			i += 1
	if len(odd) <= 1 or (len(odd) == n and n % 2):
		return -1
	if len(odd) % 2:
		arr.append(odd.pop())
	return ' '.join(map(str, odd + arr))
for _ in range(int(input())):
	print(solve1())


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	o = 0
	e = 0
	o1 = []
	e1 = []
	f = 0
	for i in a:
		if i % 2 == 0:
			e += 1
			e1.append(i)
		else:
			o += 1
			o1.append(i)
	if o < 2 or (e == 0 and o % 2 != 0):
		print(-1)
	elif e == 0 and o % 2 == 0:
		print(*o1)
	else:
		f = 1
		x1 = []
		if e > o:
			if o % 2 == 0:
				x1 = e1 + o1
			else:
				x1 = x1 + o1[0:2]
				x1 = x1 + e1
				x1 = x1 + o1[2:]
		elif o % 2 == 0:
			x1 = e1 + o1
		else:
			x1 = x1 + o1[0:2]
			x1 = x1 + e1
			x1 = x1 + o1[2:]
	if f == 1:
		print(*x1)


def solve(n, arr):
	odd = []
	even = []
	for i in range(n):
		if arr[i] % 2 == 1:
			odd.append(arr[i])
		else:
			even.append(arr[i])
	if len(odd) == 0:
		return -1
	if len(even) == 0:
		return ' '.join(map(str, odd)) if n % 2 == 0 else -1
	if len(odd) == 1:
		return -1
	if len(odd) % 2 == 0:
		return ' '.join(map(str, even + odd))
	e = even.pop()
	o = odd.pop()
	return ' '.join(map(str, even + [o] + [e] + odd))
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


t = int(input())
for _ in range(t):
	n = input()
	arr = list(map(int, input().split()))
	ae = []
	ao = []
	for i in arr:
		if i % 2 == 0:
			ae.append(i)
		else:
			ao.append(i)
	if len(ao) <= 1 or (len(ae) == 0 and len(ao) % 2 != 0):
		print(-1)
	else:
		ans = []
		if len(ao) % 2 == 0:
			ans = ao + ae
		else:
			ans = ao[:-1] + ae
			ans.append(ao[-1])
		print(*ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	v = []
	even = 0
	odd = 0
	for i in l:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd % 2 == 0 and odd != 0:
		for j in l:
			if j % 2 != 0:
				v.append(j)
		for j in l:
			if j % 2 == 0:
				v.append(j)
		print(*v)
	elif odd != 1 and odd % 2 != 0 and (even != 0):
		for j in l:
			if j % 2 != 0:
				v.append(j)
		for j in l:
			if j % 2 == 0:
				v.append(j)
		print(*v[1:], v[0])
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	(odd, even) = (0, 0)
	for i in range(n):
		if l[i] % 2:
			odd += 1
		else:
			even += 1
	if odd == 0:
		print(-1)
	elif odd % 2 == 0:
		for i in range(n):
			if l[i] % 2:
				print(l[i], end=' ')
		for i in range(n):
			if not l[i] % 2:
				print(l[i], end=' ')
		print()
	elif odd == 1 or even == 0:
		print(-1)
	else:
		i = 0
		while odd > 1:
			if l[i] % 2:
				print(l[i], end=' ')
				odd -= 1
			i += 1
		for i in range(n):
			if not l[i] % 2:
				print(l[i], end=' ')
			else:
				temp = l[i]
		print(temp)


t = int(input(''))
for i in range(0, t):
	n = int(input(''))
	lis = list(map(int, input('').split(' ')))
	o = 0
	e = 0
	ol = []
	el = []
	for i in lis:
		if i % 2 == 0:
			e = e + 1
			el.append(i)
		else:
			o = o + 1
			ol.append(i)
	if o == 0 or o == 1:
		print(-1)
	elif e == 0:
		if o % 2 == 1:
			print(-1)
		else:
			for k in ol:
				print(k, end=' ')
			print('')
	elif o % 2 == 0:
		for k in ol:
			print(k, end=' ')
		for q in el:
			print(q, end=' ')
		print('')
	elif o % 2 == 1:
		for k in ol[1:]:
			print(k, end=' ')
		for q in el:
			print(q, end=' ')
		print(ol[0])
		print('')


for i in range(int(input())):
	n = int(input())
	A = [int(k) for k in input().split()]
	o = []
	e = []
	for k in range(n):
		if A[k] % 2 == 0:
			e.append(A[k])
		else:
			o.append(A[k])
	O = len(o)
	E = len(e)
	d = []
	if O == 0 or O == 1:
		print(-1)
	elif E != 0:
		if O % 2 == 0:
			d = o + e
			print(*d)
		else:
			d = [o[0]] + e + o[1:]
			print(*d)
	elif E == 0:
		if O % 2 == 0:
			print(*o)
		else:
			print(-1)


t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	(o, e) = (0, 0)
	odd = []
	even = []
	for i in range(n):
		if arr[i] % 2 == 0:
			e += 1
			even.append(arr[i])
		else:
			o += 1
			odd.append(arr[i])
	if o <= 1:
		print(-1)
		continue
	if o % 2 == 0:
		per = odd + even
	elif o % 2 != 0 and e > 0:
		per = odd[:-1] + even + [odd[-1]]
	else:
		per = [-1]
	print(*per)


t = int(input())
for _ in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	e_c = 0
	o_c = 0
	od = []
	ev = []
	for i in li:
		if i % 2 == 0:
			e_c += 1
			ev.append(i)
		else:
			o_c += 1
			od.append(i)
	if o_c == 0:
		print(-1, end=' ')
	elif o_c == 1 and e_c == 0:
		print(li[0], end=' ')
	elif o_c == 1:
		print(-1, end=' ')
	elif o_c % 2 == 0:
		for i in od:
			print(i, end=' ')
		for i in ev:
			print(i, end=' ')
	elif o_c % 2 != 0 and e_c > 0:
		for i in range(o_c - 1):
			print(od[i], end=' ')
		for i in ev:
			print(i, end=' ')
		print(od[o_c - 1], end=' ')
	else:
		print(-1, end=' ')
	print()


import collections

def solve(nums):
	can_solve = False
	even_odd_zero = collections.defaultdict(list)
	for n in nums:
		if n == 0:
			even_odd_zero['zero'].append(n)
		elif n % 2:
			even_odd_zero['odd'].append(n)
		else:
			even_odd_zero['even'].append(n)
	res = []
	if len(even_odd_zero['odd']) >= 3 and len(even_odd_zero['odd']) % 2 == 1 and (len(even_odd_zero['even']) >= 1):
		can_solve = True
		res = [even_odd_zero['odd'][0]] + [even_odd_zero['even'][0]] + even_odd_zero['odd'][1:] + even_odd_zero['even'][1:] + even_odd_zero['zero']
	if len(even_odd_zero['odd']) >= 2 and len(even_odd_zero['odd']) % 2 == 0:
		can_solve = True
		res = even_odd_zero['odd'] + even_odd_zero['even'] + even_odd_zero['zero']
	print(' '.join(list(map(str, res)))) if can_solve else print(-1)
for _ in range(int(input())):
	N = int(input())
	nums = list(map(int, input().split()))
	solve(nums)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	(e, o) = ([], [])
	for i in l:
		if i % 2 == 0:
			e.append(i)
		else:
			o.append(i)
	k = len(o)
	if k == 0:
		print(-1)
	elif k == n:
		if k % 2 == 1:
			print(-1)
		else:
			print(*o, sep=' ')
	elif k == 1:
		print(-1)
	elif k % 2 == 1:
		k = o[-1]
		o.pop()
		print(*o, *e, k, sep=' ')
	else:
		print(*o, *e, sep=' ')


t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = [int(num) for num in input().split()]
	odds = 0
	oddslist = []
	eveslist = []
	for i in range(0, len(list1)):
		if list1[i] % 2 == 1:
			odds += 1
			oddslist.append(list1[i])
		else:
			eveslist.append(list1[i])
	if odds == 0:
		print(-1)
	elif odds == n and n % 2 == 1:
		print(-1)
	elif odds == n and n % 2 == 0:
		s = ''
		for i in range(0, len(list1)):
			s += str(list1[i]) + ' '
		print(s.strip())
	else:
		s = ''
		if odds % 2 == 0:
			for i in range(0, len(oddslist)):
				s += str(oddslist[i]) + ' '
			for i in range(0, len(eveslist)):
				s += str(eveslist[i]) + ' '
			print(s.strip())
		elif odds != 1:
			for i in range(0, len(oddslist) - 1):
				s += str(oddslist[i]) + ' '
			for i in range(0, len(eveslist)):
				s += str(eveslist[i]) + ' '
			s += str(oddslist[len(oddslist) - 1])
			print(s)
		else:
			print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ar = []
	so = 0
	se = 0
	a = []
	for i in range(n):
		if arr[i] % 2 == 1:
			so += 1
			ar.append(arr[i])
	for i in range(n):
		if arr[i] % 2 == 0:
			se += 1
			ar.append(arr[i])
	if so == 1 or so == 0 or (n % 2 == 1 and se == 0):
		print(-1)
	elif so % 2 == 0:
		print(*ar)
	elif so % 2 == 1:
		for j in range(1, n):
			a.append(ar[j])
		a.append(ar[0])
		print(*a)
	else:
		print(-1)


def permutation(arr, n):
	o = []
	e = []
	for y in arr:
		if y % 2 == 0:
			e.append(y)
		else:
			o.append(y)
	if len(o) == n and n % 2 != 0:
		return [-1]
	elif len(o) == n and n % 2 == 0:
		return arr
	elif len(e) == n:
		return [-1]
	elif len(o) == 1:
		return [-1]
	elif len(o) % 2 == 0:
		for y in e:
			o.append(y)
		return o
	else:
		ans = []
		i = 0
		while i < len(o) - 1:
			ans.append(o[i])
			i += 1
		for y in e:
			ans.append(y)
		ans.append(o[len(o) - 1])
		return ans
test_cases = int(input())
while test_cases != 0:
	data = int(input())
	data2 = list(map(int, input().split()))
	print(*permutation(data2, data))
	test_cases -= 1


def adjLove(arr):
	oddCount = 0
	oddList = []
	evenList = []
	for i in range(len(arr)):
		if arr[i] % 2 != 0:
			oddCount += 1
			oddList.append(arr[i])
		else:
			evenList.append(arr[i])
	if oddCount <= 1 or (oddCount % 2 == 1 and len(evenList) == 0):
		print(-1)
		return
	elif oddCount % 2 == 0:
		for i in range(len(oddList)):
			print(oddList[i], end=' ')
		for i in range(len(evenList)):
			print(evenList[i], end=' ')
		print()
	else:
		for i in range(len(oddList) - 1):
			print(oddList[i], end=' ')
		for i in range(len(evenList)):
			print(evenList[i], end=' ')
		print(oddList[len(oddList) - 1])
tests = int(input())
for test in range(tests):
	num = int(input())
	arr = list(map(int, input().split()))
	adjLove(arr)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().strip().split()))[:n]
	odd = []
	even = []
	for i in a:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	if len(odd) <= 1:
		print(-1)
	elif len(odd) % 2 != 0 and len(even) == 0:
		print(-1)
	elif len(odd) % 2 == 0:
		print(*odd, *even)
	else:
		for i in range(len(odd) - 1):
			print(odd[i], end=' ')
		print(*even, odd[-1])
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	dx = [int(i) for i in input().split()]
	eve = 0
	odd = 0
	for j in range(n):
		if dx[j] % 2 == 0:
			eve += 1
		else:
			odd += 1
	if odd == 0 or odd == 1:
		print(-1)
		continue
	elif odd % 2 == 0:
		dl = []
		for j in dx:
			if j % 2 == 0:
				pass
			else:
				dl.append(j)
		for j in dx:
			if j % 2 == 0:
				dl.append(j)
		dl = [str(i) for i in dl]
		print(' '.join(dl))
	elif eve > 0:
		dl = []
		dl_eve = []
		dl_odd = []
		for j in dx:
			if j % 2 == 0:
				dl_eve.append(j)
			else:
				dl_odd.append(j)
		for j in dl_odd[:-1]:
			dl.append(j)
		for j in dl_eve:
			dl.append(j)
		dl.append(dl_odd[-1])
		dl = [str(i) for i in dl]
		print(' '.join(dl))
	else:
		print(-1)
		continue


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()[:n]))
	lo = []
	le = []
	for i in l:
		if i % 2 == 0:
			le.append(i)
		else:
			lo.append(i)
	s1 = len(le)
	s2 = len(lo)
	if s2 == n and n % 2 == 1 or s2 <= 1:
		print(-1)
	else:
		if s2 % 2 == 1:
			print(lo.pop(), end=' ')
		le.extend(lo)
		print(*le)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	odd = []
	even = []
	for i in a:
		if i % 2:
			odd.append(i)
		else:
			even.append(i)
	if len(odd) <= 1 or (len(odd) == n and n % 2):
		print(-1)
	else:
		if len(odd) % 2:
			print(odd.pop(), end=' ')
		print(*even, end=' ')
		print(*odd)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	odd = sorted(list(filter(lambda i: i % 2, a)))
	even = sorted(list(filter(lambda i: not i % 2, a)))
	if odd and (not len(odd) % 2):
		a = odd + even
		print(*a)
	elif even and len(odd) >= 3:
		a = odd[:-1] + even + [odd[-1]]
		print(*a)
	else:
		print(-1)


for i in range(int(input())):
	num = int(input())
	arr = list(map(int, input().split(' ')))
	odd = []
	even = []
	for ii in arr:
		if ii % 2 != 0:
			odd.append(ii)
		else:
			even.append(ii)
	if len(odd) <= 1:
		print(-1)
	elif len(odd) % 2 == 0:
		ans = odd + even
		print(*ans)
	elif len(odd) % 2 != 0 and len(even) == 0:
		print(-1)
	else:
		k = odd.pop()
		ans = odd + even + [k]
		print(*ans)


import math, os, io, heapq
from functools import reduce
from sys import stdin, stdout
from collections import Counter, deque, defaultdict
from itertools import product
import bisect

def getList(method=int):
	return list(map(method, input().split()))

def getInt():
	return int(input())

def solve():
	(n, a) = (getInt(), getList())
	(even, odd) = ([], [])
	for v in a:
		if v % 2:
			odd.append(v)
		else:
			even.append(v)
	if not even:
		print(*(a if n % 2 == 0 else [-1]))
	elif len(odd) <= 1:
		print(-1)
	elif len(odd) % 2 == 0:
		print(*even, *odd)
	else:
		print(odd[0], *even, *odd[1:])
for _ in range(getInt()):
	solve()


T = int(input())
for _ in range(T):
	N = int(input())
	evens = []
	odds = []
	for A in input().split():
		if int(A) % 2 == 0:
			evens.append(A)
		else:
			odds.append(A)
	if len(odds) == 0:
		print(-1)
	elif len(odds) % 2 == 0:
		print(' '.join(evens + odds))
	elif len(evens) > 0 and len(odds) > 1:
		last = odds.pop()
		evens = [last, *evens]
		print(' '.join(evens + odds))
	else:
		print(-1)


def leftRotate(arr):
	first_elem = arr[0]
	for idx in range(1, len(arr)):
		arr[idx - 1] = arr[idx]
	arr[len(arr) - 1] = first_elem
	return arr

def adjLove(n, arr):
	(n_even, n_odd) = (0, 0)
	left = 0
	right = len(arr) - 1
	while left <= right:
		if arr[left] % 2 == 0:
			if arr[right] % 2 == 1:
				n_even += 1
				n_odd += 1
				(arr[left], arr[right]) = (arr[right], arr[left])
				left += 1
				right -= 1
			else:
				n_even += 1
				right -= 1
		else:
			n_odd += 1
			left += 1
	if n_even > 0 and n_odd % 2 == 0 and (n_odd > 1):
		return arr
	elif n_even == 0 and n_odd % 2 == 0:
		return arr
	elif n_even >= 1 and n_odd % 2 == 1 and (n_odd > 1):
		return leftRotate(arr)
	else:
		return None
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split(' ')))
	ans = adjLove(n, arr)
	if ans is not None:
		for num in ans:
			print(num, end=' ')
		print()
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	o = []
	e = []
	for i in l:
		if i % 2 == 0:
			e.append(i)
		else:
			o.append(i)
	if len(o) == 1 or len(o) == 0 or (len(o) % 2 == 1 and len(e) == 0):
		print(-1)
	elif len(o) % 2 == 0:
		print(*o + e)
	else:
		print(*o[:-1] + e + [o[-1]])


T = int(input())
for tc in range(T):
	N = int(input())
	arr = list(map(int, input().split(' ')))
	odd = list(filter(lambda x: x % 2 == 1, arr))
	even = list(filter(lambda x: x % 2 == 0, arr))
	oddLen = len(odd)
	if oddLen <= 1:
		print(-1)
		continue
	if oddLen == len(arr):
		if oddLen % 2 == 1:
			print(-1)
			continue
		else:
			print(*arr, sep=' ')
			continue
	if oddLen % 2 == 0:
		arr = odd + even
	else:
		arr = odd[:-1] + even
		arr.append(odd[-1])
	print(*arr, sep=' ')


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	odd = [x for x in a if x % 2 == 1]
	even = [x for x in a if x % 2 == 0]
	if len(odd) == 1 or len(odd) == 0:
		if len(even) >= 1:
			print(-1)
		else:
			print(*odd)
		continue
	if len(odd) % 2 == 0:
		print(*odd, end=' ')
		print(*even)
	elif len(even) < 1:
		print(-1)
	else:
		print(*odd[:len(odd) - 1], end=' ')
		print(even[0], end=' ')
		print(odd[len(odd) - 1], end=' ')
		print(*even[1:])


for i in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	even = []
	odd = []
	for num in array:
		if num % 2 == 0:
			even.append(num)
		else:
			odd.append(num)
	len_e = len(even)
	len_o = len(odd)
	if len_o == 0:
		print(-1)
	elif len_o % 2 == 1 and len_e == 0:
		print(-1)
	elif len_o == 1 and len_e > 0:
		print(-1)
	elif len_o % 2 == 0:
		print(*[j for j in odd], end=' ')
		print(*[j for j in even], end=' ')
		print()
	elif len_o % 2 != 0:
		print(*[j for j in odd[:len_o // 2 * 2]], end=' ')
		print(*[j for j in even], end=' ')
		print(*[j for j in odd[len_o // 2 * 2:]], end=' ')
		print()


def change(odd, even):
	l = []
	for i in range(0, len(odd) - 1):
		l.append(odd[i])
	l.append(even[0])
	l.append(odd[len(odd) - 1])
	for j in range(1, len(even)):
		l.append(even[j])
	return l

def merge(odd, even):
	l = []
	for num in odd:
		l.append(num)
	for num in even:
		l.append(num)
	return l

def solve(l):
	su = 0
	for i in range(0, len(l) - 1):
		su += l[i] * l[i + 1]
	if su % 2 == 1:
		return l
	even = []
	odd = []
	for num in l:
		if num % 2 == 0:
			even.append(num)
		else:
			odd.append(num)
	if len(odd) % 2 == 1 and len(even) != 0 and (len(odd) > 1):
		l = change(odd, even)
	elif len(odd) % 2 == 0 and len(odd) != 0:
		l = merge(odd, even)
	else:
		return -1
	return l
n = int(input())
results = []
for i in range(0, n):
	num = int(input())
	l = list(map(int, input().split()))
	out = solve(l)
	results.append(out)
for li in results:
	if li == -1:
		print(-1)
		continue
	for num in li:
		print(num, end='\t')
	print()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(le, lo) = ([], [])
	for i in l:
		if i % 2 == 0:
			le.append(i)
		else:
			lo.append(i)
	if len(lo) == 0 or len(lo) == 1:
		print(-1)
		continue
	if len(lo) % 2 == 0:
		print(*lo, *le)
	elif len(le) > 0:
		print(lo[0], lo[1], *le, end=' ')
		for i in range(2, len(lo)):
			print(lo[i], end=' ')
		print()
	else:
		print(-1)


t = int(input())
for testcases in range(t):
	number = int(input())
	arr = [int(i) for i in input().split()]
	odd1 = 0
	(even, odd) = ([], [])
	for i in range(number):
		if arr[i] % 2 == 1:
			odd1 += 1
			odd.append(arr[i])
		else:
			even.append(arr[i])
	if len(odd) <= 1:
		print('-1')
	elif len(even) == 0 and len(odd) % 2 == 1:
		print('-1')
	elif len(odd) % 2 == 0:
		for i in odd:
			print(i, end=' ')
		for j in even:
			print(j, end=' ')
	else:
		for i in range(len(odd) - 1):
			print(odd[i], end=' ')
		for j in range(len(even)):
			print(even[j], end=' ')
		print(odd[-1])
	print()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(even, odd) = ([], [])
	for i in a:
		even.append(str(i)) if i % 2 == 0 else odd.append(str(i))
	if even == []:
		print(' '.join(odd) if len(odd) % 2 == 0 else -1)
	elif len(odd) == 1 or odd == []:
		print(-1)
	else:
		res = odd + even if len(odd) % 2 == 0 else odd[0:1] + even + odd[1:]
		print(*res)


from sys import stdin
input = stdin.readline

def answer():
	(odd, even) = ([], [])
	for i in range(n):
		if a[i] & 1:
			odd.append(a[i])
		else:
			even.append(a[i])
	(size1, size2) = (len(odd), len(even))
	ans = []
	if size1 & 1 == 0:
		if len(odd) <= 1:
			return [-1]
		ans += odd + even
	else:
		if len(even) == 0:
			return [-1]
		if len(odd) <= 1:
			return [-1]
		ans.append(odd.pop())
		ans.append(even.pop())
		ans += odd
		ans += even
	return ans
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(*answer())


from sys import stdin
inp = stdin.readline
T = int(inp())
for tx in range(T):
	N = int(input())
	Ays = list(map(int, inp().split()))
	ev = []
	od = []
	for a in Ays:
		if a % 2:
			od.append(a)
		else:
			ev.append(a)
	if len(ev) == 0:
		if len(od) % 2 == 0:
			print(*Ays)
		else:
			print(-1)
	elif len(od) < 2:
		print(-1)
	elif len(od) % 2 == 0:
		print(*od, *ev)
	else:
		spare = od.pop()
		print(*od, *ev, spare)


def solve_v2(_data):
	data = list(map(int, _data.split()))
	(even, odd) = ([], [])
	for i in data:
		even.append(i) if i & 1 == 0 else odd.append(i)
	if len(odd) <= 1 or (len(odd) & 1 and len(even) == 0):
		print(-1)
	elif len(odd) & 1 != 1:
		print(*odd, *even)
	else:
		if len(odd) % 2:
			print(odd.pop(), end=' ')
		print(*even, end=' ')
		print(*odd)
T = int(input())
for i in range(T):
	N = int(input())
	A = input()
	solve_v2(A)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	(odd_list, even_list) = ([], [])
	for i in range(N):
		if A[i] % 2 == 0:
			even_list.append(A[i])
		else:
			odd_list.append(A[i])
	if len(odd_list) <= 1:
		print(-1)
	elif len(odd_list) % 2 == 0:
		for items in odd_list:
			print(items, end=' ')
		for items in even_list:
			print(items, end=' ')
	elif len(odd_list) % 2 != 0:
		if len(even_list) == 0:
			print(-1)
		elif len(even_list) >= 1:
			for i in range(len(odd_list) - 1):
				print(odd_list[i], end=' ')
			for items in even_list:
				print(items, end=' ')
			print(odd_list[-1], end=' ')
	print()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	o = []
	e = []
	for i in a:
		if i & 1 == 0:
			e.append(i)
		else:
			o.append(i)
	if len(o) <= 1:
		print(-1)
	elif len(o) & 1 != 0 and len(e) == 0:
		print(-1)
	elif len(o) & 1 == 0:
		print(*o, *e)
	else:
		for i in range(len(o) - 1):
			print(o[i], end=' ')
		print(*e, o[-1])


T = int(input())

def prd_sum(list):
	sum = 0
	for i in range(len(list) - 1):
		sum += list[i] * list[i + 1]
	return sum

def operation1(list):
	(even, odd) = ([], [])
	for I in range(len(list)):
		if list[I] % 2 == 0:
			even.append(list[I])
		elif list[I] % 2 != 0:
			odd.append(list[I])
	odd.sort(reverse=True)
	even.sort(reverse=True)
	(a, b) = (len(even), len(odd))
	result = []
	if b % 2 == 0:
		for __ in range(b):
			result.append(odd[__])
		for __ in range(a):
			result.append(even[__])
	else:
		for __ in range(b - 1):
			result.append(odd[__])
		for __ in range(a):
			result.append(even[__])
		result.append(odd[b - 1])
	return result

def goornot(list):
	(even, odd) = ([], [])
	for I in range(len(list)):
		if list[I] % 2 == 0:
			even.append(list[I])
		elif list[I] % 2 != 0:
			odd.append(list[I])
	(a, b) = (len(even), len(odd))
	return (a, b)
for _ in range(T):
	A = int(input())
	numbers = list(map(int, input().split()))
	(b, a) = goornot(numbers)
	if a == 1 and b != 0 or a == 0 or (a == len(numbers) and a != 1 and (a % 2 != 0) or (a != 1 and a % 2 != 0 and (b == 0))):
		print('-1')
	elif prd_sum(numbers) % 2 != 0:
		print(*numbers)
	else:
		print(*operation1(numbers))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if len(a) == 1:
		print(*a)
		continue
	b = [i for i in a if i % 2 == 1]
	c = [i for i in a if i % 2 == 0]
	if len(b) == 0:
		print(-1)
		continue
	if len(b) % 2 == 0:
		d = b + c
		print(*d)
	elif len(c) == 0 or len(b) == 1:
		print(-1)
	else:
		d = b[:len(b) - 1]
		d += [c[0]]
		d += [b[-1]]
		if len(c) > 1:
			d += c[1:]
		print(*d)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(e, o) = (0, 0)
	l1 = []
	l2 = []
	for i in l:
		if i % 2 == 0:
			e += 1
			l1.append(i)
		else:
			o += 1
			l2.append(i)
	if o <= 1:
		print(-1)
	elif o % 2 == 0:
		for i in l2:
			print(i, end=' ')
		for i in l1:
			print(i, end=' ')
		print()
	elif e == 0:
		print(-1)
	else:
		for i in range(len(l2) - 1):
			print(l2[i], end=' ')
		for i in l1:
			print(i, end=' ')
		print(l2[len(l2) - 1])


for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	e = o = 0
	even = []
	odd = []
	for i in l:
		if i % 2 == 0:
			e += 1
			even.append(i)
		else:
			o += 1
			odd.append(i)
	if e == x:
		print(-1)
		continue
	if o == x:
		if o % 2 == 0:
			print(*l)
		else:
			print(-1)
		continue
	if o % 2 == 0:
		print(*odd + even)
	else:
		if o <= 1:
			print(-1)
			continue
		for i in odd[:-1]:
			print(i, end=' ')
		print(*even, end=' ')
		print(odd[-1])


def print_arr(arr):
	res = ''
	for x in arr:
		res = res + str(x) + ' '
	print(res[:-1])
T = int(input())
for _ in range(T):
	N = int(input())
	arr = []
	temp = input()
	temp = temp.split(' ')
	arr = [int(x) for x in temp]
	odds = []
	eves = []
	for n in arr:
		if n % 2 == 0:
			eves.append(n)
		else:
			odds.append(n)
	if len(odds) < 2:
		print('-1')
	elif len(odds) % 2 == 0:
		temp = odds + eves
		print_arr(temp)
	elif len(eves) > 0:
		temp = odds[:-1] + eves + [odds[-1]]
		print_arr(temp)
	else:
		print('-1')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(o, e) = ([], [])
	for i in l:
		if i % 2:
			o.append(i)
		else:
			e.append(i)
	(on, en) = (len(o), len(e))
	if on <= 1:
		print(-1)
	elif en == 0:
		if on % 2:
			print(-1)
		else:
			print(*o)
	else:
		if on % 2:
			print(o.pop(), end=' ')
		print(*e, end=' ')
		print(*o)


for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	(odd, even) = ([], [])
	for a in A:
		if a % 2:
			odd.append(a)
		else:
			even.append(a)
	if not odd:
		print(-1)
	elif len(odd) % 2 == 0:
		print(*odd, *even, sep=' ')
	elif len(odd) == 1:
		print(-1)
	elif not even:
		print(-1)
	else:
		print(odd[0], even[0], *odd[1:], *even[1:])


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ol = []
	el = []
	flag = 0
	on = 0
	en = 0
	for j in a:
		if j % 2 == 0:
			el.append(j)
			en += 1
		else:
			ol.append(j)
			on += 1
	if on % 2 == 0:
		res = ol + el
		flag = 1
	elif en >= 1:
		res = ol[:on - 1] + el + [ol[-1]]
		flag = 1
	if on <= 1:
		flag = 0
	if flag == 0:
		print(-1)
	else:
		for i in range(n):
			if i == n - 1:
				print(res[i])
			else:
				print(res[i], end=' ')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	result = []
	oddcount = 0
	for i in a:
		if i % 2 != 0:
			oddcount += 1
			result.append(i)
	for i in a:
		if i % 2 == 0:
			result.append(i)
	if oddcount <= 1:
		print(-1)
	elif oddcount == n:
		if n % 2 != 0:
			print(-1)
		else:
			print(*a)
	elif oddcount % 2 == 0:
		print(*result)
	else:
		result.append(result.pop(0))
		print(*result)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	l2 = []
	for i in l:
		if i % 2 == 0:
			l1.append(i)
		else:
			l2.append(i)
	if len(l2) <= 1 or (len(l2) == n and n % 2):
		print(-1)
	else:
		if len(l2) % 2:
			print(l2.pop(), end=' ')
		print(*l1, end=' ')
		print(*l2)


t = int(input())
for i in range(t):
	a = int(input())
	c = [int(y) for y in input().split()]
	m = 0
	n = 0
	e = []
	o = []
	for j in c:
		if int(j) % 2 == 0:
			e.append(int(j))
			m += 1
		else:
			o.append(int(j))
			n += 1
	if n <= 1:
		print(-1)
	elif n % 2 == 0:
		print(*o, *e)
	elif n % 2 == 1 and m == 0:
		print(-1)
	else:
		print(*o[:1], *e, *o[1:])


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split(' ')]
	ec = 0
	e = []
	oc = 0
	o = []
	for i in arr:
		if i % 2 == 0:
			ec += 1
			e += [i]
		else:
			oc += 1
			o += [i]
	if oc <= 1:
		print(-1)
	elif oc % 2 == 0:
		print(*o, *e)
	elif oc % 2 == 1 and ec == 0:
		print(-1)
	else:
		print(*o[:-1], *e, o[-1])


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0] * n
	(od, ev) = (0, 0)
	for i in a:
		if i % 2 == 1:
			b[od] = i
			od += 1
		else:
			b[-ev - 1] = i
			ev += 1
	if od < 2 or (od == n and n % 2 == 1):
		print(-1)
		continue
	if od % 2 == 1:
		(b[od - 1], b[-ev]) = (b[-ev], b[od - 1])
	print(' '.join(map(str, b)))


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()
	od = 0
	l1 = []
	l2 = []
	for i in l:
		if i % 2 != 0:
			od += 1
			l2.append(i)
		else:
			l1.append(i)
	if od == 0 or od == 1:
		print(-1)
	elif od % 2 == 0:
		print(*l2, end=' ')
		print(*l1)
	elif len(l1) > 0:
		print(*l2[:len(l2) - 1], end=' ')
		print(l1[0], end=' ')
		print(l2[-1], end=' ')
		print(*l1[1:])
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	inp = list(map(int, input().split()))
	odd = []
	even = []
	for (i, item) in enumerate(inp):
		if item % 2:
			odd.append(item)
		else:
			even.append(item)
	if len(odd) < 2:
		print(-1)
	elif len(odd) % 2 == 0:
		print(*odd + even)
	elif even:
		print(*odd[:-1] + even + [odd[-1]])
	else:
		print(-1)


n = int(input())
for _ in range(n):
	a = int(input())
	x = list(map(int, input().split(' ')))
	(odd, even) = ([], [])
	for i in range(a):
		if x[i] % 2 == 0:
			even.append(x[i])
		else:
			odd.append(x[i])
	if len(odd) <= 1:
		print('-1')
	elif len(even) == 0 and len(odd) % 2 == 1:
		print('-1')
	elif len(odd) % 2 == 0:
		for i in odd:
			print(i, end=' ')
		for j in even:
			print(j, end=' ')
	else:
		for i in range(len(odd) - 1):
			print(odd[i], end=' ')
		for j in range(len(even)):
			print(even[j], end=' ')
		print(odd[-1])
	print()


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	o = []
	e = []
	for i in a:
		if i & 1:
			o.append(i)
		else:
			e.append(i)
	ol = len(o)
	el = len(e)
	if ol == 1 or el == n or (ol & 1 and el == 0):
		print(-1)
	elif ol & 1:
		print(*o[:-1] + e + [o[-1]])
	else:
		print(*o + e)


for _ in range(int(input())):
	a = int(input())
	b = [int(i) for i in input().split()]
	odd = []
	even = []
	for i in b:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	if len(odd) <= 1 or (len(odd) == a and a % 2 != 0):
		print(-1)
	else:
		if len(odd) % 2 == 1:
			print(odd.pop(0), end=' ')
		for i in even:
			print(i, end=' ')
		for i in odd:
			print(i, end=' ')
		print()


t = int(input())

def adLove(arr):
	even = []
	odd = []
	ec = 0
	oc = 0
	for i in arr:
		if i % 2 == 0:
			ec += 1
			even.append(i)
		else:
			oc += 1
			odd.append(i)
	if oc <= 1:
		print(-1)
	elif oc % 2 == 0:
		res = odd + even
		print(*res)
	elif ec == 0:
		print(-1)
	else:
		res = odd[:oc - 1] + even + [odd[oc - 1]]
		print(*res)
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	adLove(arr)


n = int(input())
while n > 0:
	n -= 1
	m = int(input())
	t = list(map(int, input().split()))
	odd = []
	even = []
	for i in range(len(t)):
		if t[i] % 2 == 0:
			even.append(t[i])
		else:
			odd.append(t[i])
	if len(odd) <= 1 or (len(even) == 0 and m % 2 == 1):
		print(-1)
	elif len(even) == 0:
		for i in range(m):
			print(odd[i], end=' ')
	else:
		res = []
		n1 = 0
		n2 = 0
		if len(odd) % 2 == 1 and len(odd) > 0:
			res.append(odd[0])
			res.append(even[0])
			n2 += 1
			n1 += 1
		while n1 < len(even):
			res.append(even[n1])
			n1 += 1
		while n2 < len(odd):
			res.append(odd[n2])
			n2 += 1
		print(*res, sep=' ')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(e, o) = (0, 0)
	(ee, oo) = ([], [])
	for i in a:
		if i % 2 == 0:
			e += 1
			ee.append(i)
		else:
			o += 1
			oo.append(i)
	if o <= 1:
		print(-1)
	elif n == o:
		if n % 2 == 0:
			print(*a, sep=' ')
		else:
			print(-1)
	elif o % 2 == 0:
		ans = oo + ee
		print(*ans, sep=' ')
	else:
		ans = oo[:-1] + ee + [oo[-1]]
		print(*ans, sep=' ')


from sys import stdin
from math import ceil
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	even = []
	odd = []
	for ele in li:
		if ele % 2 == 0:
			even.append(ele)
		else:
			odd.append(ele)
	if len(even) == 0:
		if len(odd) % 2 == 0:
			print(*odd)
		else:
			print(-1)
	elif len(odd) == 0:
		print(-1)
	elif len(odd) == 1:
		print(-1)
	elif len(odd) % 2 == 0:
		print(*odd + even)
	else:
		print(*odd[:len(odd) - 1] + even + [odd[-1]])


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	o_list = []
	e_list = []
	o_count = 0
	e_count = 0
	for num in nums:
		if num % 2 == 0:
			e_list.append(num)
			e_count += 1
		else:
			o_list.append(num)
			o_count += 1
	if o_count < 2:
		print(-1)
	elif o_count % 2 == 0 and o_count != 0:
		ans_list = o_list + e_list
		for ans in ans_list:
			print(ans, end=' ')
		print()
	elif e_count > 0:
		e_list.append(o_list[0])
		o_list.pop(0)
		ans_list = o_list + e_list
		for ans in ans_list:
			print(ans, end=' ')
		print()
	else:
		print(-1)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	even = []
	odd = []
	for i in arr:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	res = []
	flag = 0
	if len(odd) % 2 == 0:
		res += odd
	else:
		flag = 1
		res += odd[:len(odd) - 1]
	res += even
	if flag == 1:
		res += [odd[-1]]
	ans = 0
	for i in range(len(res) - 1):
		ans += res[i] * res[i + 1]
	if ans % 2 != 0:
		for i in res:
			print(i, end=' ')
		print()
	else:
		print(-1)


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	odd = []
	even = []
	for i in l:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	if len(odd) >= 2 and (len(odd) % 2 != 0 and len(even) >= 1 or len(odd) % 2 == 0):
		if len(odd) % 2 == 0:
			ll = odd[:] + even[:]
		else:
			ll = odd[:-1] + even + [odd[-1]]
		for i in ll:
			print(i, end=' ')
	else:
		print(-1)
	print()


t = int(input())
for _ in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	odd = []
	even = []
	for i in l1:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	if len(odd) <= 1:
		print('-1')
	elif len(odd) % 2 != 0 and len(even) == 0:
		print('-1')
	elif len(odd) % 2 == 0:
		for i in odd:
			print(i, sep=' ', end=' ')
		for j in even:
			print(j, sep=' ', end=' ')
		print()
	elif len(odd) % 2 != 0 and len(even) >= 1:
		for i in range(len(odd) - 1):
			print(odd[i], sep=' ', end=' ')
		for j in even:
			print(j, sep=' ', end=' ')
		print(odd[len(odd) - 1])


for h in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	even = []
	odd = []
	q = []
	(e, o) = (0, 0)
	for l in li:
		if l % 2 == 0:
			e += 1
			even.append(l)
		else:
			o += 1
			odd.append(l)
	if o <= 1 or (o % 2 != 0 and e == 0):
		print(-1)
	else:
		if o % 2 == 0:
			q.extend(odd)
			q.extend(even)
		else:
			q.extend(odd[:-1])
			q.extend(even)
			q.append(odd[-1])
		print(*q)


T = int(input())
for tc in range(T):
	n = int(input())
	a = input().split()
	a_odd = []
	odd = 0
	a_even = []
	even = 0
	for i in range(n):
		num = a[i]
		if int(num) % 2 == 1:
			a_odd.append(num)
			odd += 1
		else:
			a_even.append(num)
			even += 1
	if odd <= 1:
		print(-1)
	elif odd % 2 == 0:
		print(' '.join(a_odd), end=' ')
		print(' '.join(a_even))
	elif not even:
		print(-1)
	else:
		print(' '.join(a_odd[:odd - 1]), end=' ')
		print(' '.join(a_even), end=' ')
		print(a_odd[odd - 1])


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	odd = []
	even = []
	for i in arr:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	if len(even) == n or len(odd) == 1:
		print(-1)
	elif len(odd) == n and len(odd) % 2 != 0:
		print(-1)
	elif len(odd) % 2 == 0:
		print(*odd + even)
	else:
		for i in range(len(odd) - 1):
			print(odd[i], end=' ')
		print(even[0], end=' ')
		print(odd[-1], end=' ')
		for i in range(1, len(even)):
			print(even[i], end=' ')
		print()


t = int(input())
while t > 0:
	odd = []
	even = []
	n = int(input())
	l = list((int(x) for x in input().split()))
	for i in l:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	a = len(odd)
	b = len(even)
	if len(odd) == n and n % 2 == 1 or len(odd) < 2:
		print(-1)
	elif len(odd) % 2 == 1:
		print(*odd[:-1], end=' ')
		print(*even, end=' ')
		print(odd[-1])
	else:
		print(*odd, end=' ')
		print(*even)
	t = t - 1


from bisect import bisect_left
from re import sub
from typing import DefaultDict
import math
from collections import defaultdict
from math import sqrt
import collections
from sys import maxsize
from itertools import combinations_with_replacement
import sys

def sieve_erasthones(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def count_factors(n):
	i = 1
	c = 0
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				c += 1
			else:
				c += 2
		i += 1
	return c

def ncr_modulo(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def dict_ele_count(l):
	d = DefaultDict(lambda : 0)
	for ele in l:
		d[ele] += 1
	return d

def max_in_dict(d):
	maxi = 0
	for ele in d:
		if d[ele] > maxi:
			maxi = d[ele]
	return maxi

def element_count(s):
	l = []
	k = s[0]
	c = 0
	for ele in s:
		if ele == k:
			c += 1
		else:
			l.append([k, c])
			k = ele
			c = 1
	l.append([k, c])
	return l

def modular_exponentiation(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 != 0:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def number_of_primefactor(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
	return len(set(l))

def twosum(a, n, x):
	rem = []
	for i in range(x):
		rem.append(0)
	for i in range(n):
		if a[i] < x:
			rem[a[i] % x] += 1
	for i in range(1, x // 2):
		if rem[i] > 0 and rem[x - i] > 0:
			return True
	if i >= x // 2:
		if x % 2 == 0:
			if rem[x // 2] > 1:
				return True
			else:
				return False
		elif rem[x // 2] > 0 and rem[x - x // 2] > 0:
			return True
		else:
			return False

def divSum(num):
	result = 0
	i = 2
	while i <= math.sqrt(num):
		if num % i == 0:
			if i == num / i:
				result = result + i
			else:
				result = result + (i + num / i)
		i = i + 1
	return result + 1 + num

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	x = []
	y = []
	for ele in l:
		if ele % 2 == 1:
			x.append(ele)
		else:
			y.append(ele)
	if len(x) <= 1:
		print(-1)
	elif len(x) % 2 == 1 and len(y) == 0:
		print(-1)
	elif len(x) % 2 == 0:
		y += x
		print(*y)
	else:
		temp = y[1:] + [x[0]] + [y[0]] + x[1:]
		print(*temp)
for _ in range(int(input())):
	solve()


inputs = int(input())
for i in range(inputs):
	input_length = input()
	if input_length == 1:
		print(-1)
		continue
	arr = list(map(int, input().split()))
	odd = []
	even = []
	out = []
	for i in arr:
		if i % 2:
			odd.append(i)
		else:
			even.append(i)
	if not odd:
		print(-1)
		continue
	if not len(odd) % 2:
		even += odd
		out = even
	else:
		if len(even) == 0 or len(odd) == 1:
			print(-1)
			continue
		out.append(odd[0])
		out += even
		out += odd[1:]
	print(*out, sep=' ')