Read problems statements in [Russian] and [Bengali].

An array is called *lovely* if the sum of absolute differences of each adjacent pair of elements is odd; formally, the array S of size m is lovely if \sum_{i=1}^{m-1} |S_{i}-S_{i+1}| is odd.

You are given an array A of N integers. You need to reorder the array in any manner such that the array becomes lovely. If there is no reordering operation that makes the array lovely, 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, print a single line containing N integers denoting the modified array which is lovely, or -1 if it is not possible.

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

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

----- Sample Input 1 ------ 
2
6
3 7 10 1 2 12
2
1 3

----- Sample Output 1 ------ 
1 2 3 10 7 12
-1

----- explanation 1 ------ 
- For the first test case, the sum is $|1-2| + |2-3| + |3-10| + |10-7| + |7-12| = 1+1+7+3+5 = 17$ which is odd.

- For the second test case, $|1-3| = 2$ which is even. There is no array that can satisfy the above condition.

Difficulty: MEDIUM
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
for I in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	r1 = []
	r2 = []
	for i in range(n):
		if a[i] % 2:
			r1.append(a[i])
		else:
			r2.append(a[i])
	if r1 == [] or r2 == []:
		print(-1)
	else:
		print(*r1 + r2)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(p, q) = ([], [])
	for i in range(n):
		if a[i] % 2:
			p.append(a[i])
		else:
			q.append(a[i])
	if p == [] or q == []:
		print(-1)
	else:
		print(*p + q)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	supp = []
	for i in l:
		if i & 1:
			supp.insert(0, i)
		else:
			supp.append(i)
	if abs(supp[0] - supp[-1]) & 1:
		print(*supp)
	else:
		print(-1)


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


import numpy as np
t = int(input())
for dfshaf in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	eve = 0
	evel = []
	odd = 0
	oddl = []
	for i in arr:
		if i % 2:
			odd += 1
			oddl.append(i)
		else:
			eve += 1
			evel.append(i)
	if odd != 0 and eve != 0:
		print(*evel + oddl)
	else:
		print(-1)


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


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ev = []
	od = []
	for j in l:
		if j % 2 == 0:
			ev.append(j)
		else:
			od.append(j)
	if len(ev) == len(l):
		print(-1)
	elif len(od) == len(l):
		print(-1)
	else:
		for j in range(len(od)):
			print(od[j], end=' ')
		for j in range(len(ev)):
			print(ev[j], end=' ')
		print()


(a1, a2) = (0, 1)
for _ in range(int(input())):
	n = int(input())
	n1 = list(map(int, input().strip().split()))
	n1.sort()
	n2 = [i for i in n1 if i % 2]
	n3 = [i for i in n1 if i % 2 == 0]
	(o, e) = (len(n2), len(n3))
	if o == 0 or e == 0:
		print(-1)
	else:
		print(*n2, *n3)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	xodd = [i for i in lst if i % 2 == 1]
	xeven = [i for i in lst if i % 2 == 0]
	l1 = len(xodd)
	l2 = len(xeven)
	if l2 == 0 or l1 == 0:
		print(-1)
	else:
		x = xeven + xodd
		print(*x)


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


for i in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	list2 = []
	list3 = []
	for x in list1:
		if x % 2 == 0:
			list2.append(x)
		else:
			list3.append(x)
	if len(list2) != 0 and len(list3) != 0:
		list2 += list3
		for z in list2:
			print(z, end=' ')
		print('')
	else:
		print(-1)


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


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	od = []
	ev = []
	sod = 0
	sev = 0
	for i in l:
		if i % 2 == 0:
			ev.append(i)
		else:
			od.append(i)
	if len(ev) == 0 or len(od) == 0:
		print(-1)
	else:
		for o in range(len(od) - 1):
			sod = sod + abs(od[o] - od[o + 1])
		for e in range(len(ev) - 1):
			sev = sev + abs(ev[e] - ev[e + 1])
		if (sev + sod) % 2 != 0:
			print(-1)
		else:
			for o in od:
				print(o, end=' ')
			for e in ev:
				print(e, end=' ')
			print()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	no = ne = 0
	for val in lst:
		if val % 2:
			no += 1
		else:
			ne += 1
	if no == 0 or ne == 0:
		print(-1)
	else:
		for val in lst:
			if val % 2:
				print(val, end=' ')
		for val in lst:
			if val % 2 == 0:
				print(val, end=' ')
		print()


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


a = int(input())
for i in range(a):
	N = int(input())
	array = list(map(int, input().split()))
	odd = 0
	even = 0
	Odd = []
	Even = []
	for k in array:
		if k % 2 == 0:
			even += 1
			Even.append(k)
		else:
			odd += 1
			Odd.append(k)
	if even == N or odd == N:
		print(-1)
		continue
	print(*Odd + Even)


tc = int(input().strip())
for t in range(tc):
	n = int(input().strip())
	arr = list(map(int, input().split()))
	(evens, odds) = ([], [])
	for i in arr:
		if i % 2 == 0:
			evens.append(i)
		else:
			odds.append(i)
	if len(evens) == 0 or len(odds) == 0:
		print(-1)
	else:
		for i in odds + evens:
			print(i, end=' ')
		print()


for _ in range(int(input())):
	n = int(input())
	list1 = [int(x) for x in input().split()]
	even = []
	odd = []
	for i in range(n):
		if list1[i] % 2 == 0:
			even.append(list1[i])
		else:
			odd.append(list1[i])
	if len(odd) == 0 or len(even) == 0:
		print(-1)
	else:
		answer = even + odd
		answer_to_str = ' '.join([str(elem) for elem in answer])
		print(answer_to_str)


import os, sys, io, math
from re import *
from math import *
from array import *
from heapq import *
from bisect import *
from functools import *
from itertools import *
from statistics import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IP = lambda : map(int, input().split())
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	(n, l) = (IN(), I())
	(a, b) = ([], [])
	for i in l:
		if i & 1:
			a.append(i)
		else:
			b.append(i)
	if a == [] or b == []:
		print(-1)
	else:
		print(*a + b)


t = int(input())
for _ in range(t):
	n = int(input())
	list1 = list(map(int, input().split()))
	list_even = []
	list_odd = []
	for i in range(n):
		if list1[i] % 2 == 0:
			list_even.append(list1[i])
		else:
			list_odd.append(list1[i])
	if len(list_even) == n or len(list_odd) == n:
		print(-1)
	else:
		s = ''
		for i in range(len(list_odd)):
			s = s + str(list_odd[i]) + ' '
		for i in range(len(list_even)):
			s = s + str(list_even[i]) + ' '
		print(s)


for _ in range(int(input())):
	n = int(input())
	mydict = {0: [], 1: []}
	for i in map(int, input().split()):
		if i % 2 == 0:
			mydict[0].append(i)
		else:
			mydict[1].append(i)
	a = len(mydict[0])
	b = n - a
	if min(a, b) == 0:
		print(-1)
	else:
		print(mydict[0][0], end=' ')
		for i in mydict[0][1:] + mydict[1][:-1]:
			print(i, end=' ')
		print(mydict[1][-1])


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


from collections import deque
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ae = deque()
	ao = deque()
	for i in a:
		if i % 2 == 0:
			ae.append(i)
		else:
			ao.append(i)
	if len(ae) == 0 or len(ao) == 0:
		print(-1)
	else:
		l = deque()
		for i in ae:
			l.append(i)
		for i in ao:
			l.append(i)
		for i in l:
			print(i, end=' ')
		print()


for _ in range(int(input())):
	N = int(input())
	l = list(map(int, input().split()))
	odd_list = []
	even_list = []
	for x in l:
		if x % 2 == 0:
			even_list.append(x)
		else:
			odd_list.append(x)
	if len(even_list) == 0 or len(odd_list) == 0:
		print(-1)
	else:
		for x in even_list:
			print(x, end=' ')
		for x in odd_list:
			print(x, end=' ')
		print()


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


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	even_arr = []
	odd_arr = []
	for j in arr:
		if j & 1:
			odd_arr.append(j)
		else:
			even_arr.append(j)
	if len(even_arr) == 0 or len(odd_arr) == 0:
		print(-1)
	else:
		print(*even_arr, *odd_arr)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	(o, e) = (0, 0)
	New = []
	for j in A:
		if j % 2 == 0:
			e += 1
			New = [j] + New
		else:
			o += 1
			New.append(j)
	if o == 0 or e == 0:
		print(-1)
	else:
		for j in New:
			print(j, end=' ')
		print('')


def soln(n, arr):
	odds = []
	eves = []
	for i in arr:
		if i & 1:
			odds.append(i)
		else:
			eves.append(i)
	if not len(odds) or not len(eves):
		return [-1]
	return eves + odds
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(*soln(n, arr))


for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	evens = []
	odds = []
	for i in range(n):
		if array[i] & 1:
			odds.append(array[i])
		else:
			evens.append(array[i])
	if len(odds) == 0 or len(evens) == 0:
		print(-1)
		continue
	print(*evens, *odds)


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


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().lstrip().split()))
	even = []
	odd = []
	li = []
	j = 0
	for i in range(n):
		if arr[i] % 2 == 0:
			even.append(arr[i])
		else:
			odd.append(arr[i])
	if len(even) == 0 or len(odd) == 0:
		print(-1)
	else:
		for i in range(len(even)):
			li.append(even[i])
		for j in range(len(odd)):
			li.append(odd[j])
		print(*li, sep=' ')


n = int(input())
for i in range(n):
	x = int(input())
	arr = list(map(int, input().lstrip().split()))
	even = []
	odd = []
	lovely = []
	j = 0
	for f in range(x):
		if arr[f] % 2 == 0:
			even.append(arr[f])
		else:
			odd.append(arr[f])
	if len(even) == 0 or len(odd) == 0:
		print(-1)
	else:
		for f in range(len(even)):
			lovely.append(even[f])
		for j in range(len(odd)):
			lovely.append(odd[j])
		print(*lovely, sep=' ')


tests = int(input())
for t in range(tests):
	N = int(input())
	arr = map(int, input().split(' '))
	counts = {'e': [], 'o': []}
	for i in arr:
		if i % 2 == 0:
			counts['e'].append(i)
		else:
			counts['o'].append(i)
	evens = len(counts['e'])
	odds = len(counts['o'])
	new_arr = []
	if odds == 0 or evens == 0:
		print(-1)
	else:
		for i in range(evens):
			new_arr.append(str(counts['e'][i]))
		for i in range(odds):
			new_arr.append(str(counts['o'][i]))
		print(' '.join(new_arr))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	el = []
	ol = []
	ec = 0
	oc = 0
	for i in l:
		if i % 2 == 0:
			el.append(i)
			ec += 1
		else:
			ol.append(i)
			oc += 1
	if oc == 0 or ec == 0:
		print(-1)
	else:
		print(*el, *ol)


t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = []
	d = []
	for i in a:
		if i % 2 == 0:
			c.append(i)
		else:
			d.append(i)
	if len(d) == 0 or len(c) == 0:
		print(-1)
	else:
		for x in c + d:
			print(x, end=' ')
		print()


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	odd = [ai for ai in a if ai % 2 == 1]
	even = [ai for ai in a if ai % 2 == 0]
	if len(odd) == 0 or (len(even) == 0 and len(odd) != 1):
		print(-1)
	else:
		print(*odd, *even)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	p = []
	q = []
	print()
	for i in l:
		if i % 2 == 0:
			p.append(i)
		else:
			q.append(i)
	if len(p) == 0 or len(q) == 0:
		print(-1)
	else:
		for x in p + q:
			print(x, end=' ')


def isEven(num):
	return not num & 1

def adjacent(arr, n):
	odd = []
	even = []
	for el in arr:
		if isEven(el):
			even.append(el)
		else:
			odd.append(el)
	if not odd or not even:
		return [-1]
	else:
		return even + odd
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(*adjacent(arr, n))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	el = []
	ol = []
	for i in l:
		if i % 2 == 0:
			el.append(i)
		else:
			ol.append(i)
	if len(ol) == 0:
		print(-1)
	elif len(el) == 0 and len(ol) != 1:
		print(-1)
	else:
		print(*ol, *el)


t = int(input())
for i in range(t):
	n1 = int(input())
	list1 = list(map(int, input().split()))
	list1.sort()
	sum1 = [i for i in list1 if i % 2 != 0]
	sum2 = n1 - len(sum1)
	l1 = []
	l2 = []
	if len(sum1) == n1:
		print(-1)
	elif sum2 == n1:
		print(-1)
	else:
		for i in list1:
			if i % 2 != 0:
				l1.append(i)
			else:
				l2.append(i)
		l2.extend(l1)
		print(*l2)


t = int(input())
for _ in range(t):
	n = int(input())
	num = list(map(int, input().split()))
	(e, o) = ([], [])
	for x in num:
		if x % 2 == 0:
			e.append(x)
		else:
			o.append(x)
	if len(o) == 0 or len(e) == 0:
		print(-1)
	else:
		for x in o:
			print(x, end=' ')
		for x in e:
			print(x, end=' ')
		print('')


def out(x):
	for i in x:
		print(i, end=' ')
	print('')
ntc = int(input())
for tc in range(ntc):
	length = int(input())
	arr = [int(x) for x in input().split()]
	arrodd = [x for x in arr if x % 2 == 1]
	arreven = [x for x in arr if x % 2 == 0]
	if len(arrodd) == 0 or len(arreven) == 0:
		print(-1)
		continue
	x = arrodd + arreven
	out(x)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = [a & 1 for a in A]
	if sum(B) in [0, N]:
		print(-1)
		continue
	B = list(enumerate(B))
	B.sort(key=lambda x: x[1])
	print(*[A[b[0]] for b in B])