You are given an integer N. Construct a permutation A of length N which is attractive.

A permutation is called attractive if the [bitwise XOR] of all absolute differences of adjacent pairs of elements is equal to 0.

Formally, a permutation A = [A_{1}, A_{2}, \ldots, A_{N}] of length N is said to be attractive if:

|A_{1}-A_{2}|  \oplus |A_{2}-A_{3}| \oplus \ldots \oplus |A_{N-1} - A_{N}| = 0

where \oplus denotes the bitwise XOR operation.

Output any attractive permutation of length N. If no attractive permutation exists, print -1 instead.

Note: A permutation of length N is an array A = [A_{1}, A_{2}, \ldots, A_{N}] such that every integer from 1 to N occurs exactly once in A. For example, [1, 2, 3] and [2, 3, 1] are permutations of length 3, but [1, 2, 1], [4, 1, 2], and [2, 3, 1, 4] are not.

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

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of a single line of input, containing one integer N.

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

For each test case, output on a single line an attractive permutation of N integers, or -1 if no attractive permutation exists.

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

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
- Sum of $N$ over all cases won't exceed $2 \cdot 10^{5}$.

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

----- explanation 1 ------ 
Test Case $1$: $ |3-2| \oplus |2-1|  =  1 \oplus 1 = 0$

Note that there are other correct answers — for example, $[1, 2, 3]$ would also be accepted as correct.

Test Case $2$: $ |5-2| \oplus |2-3| \oplus |3-6| \oplus |6-4| \oplus |4-1| = 3 \oplus 1 \oplus 3 \oplus 2 \oplus 3 = 0$

Source: codechef | Difficulty: MEDIUM
Tags: Bit manipulation

Mathematics


Solutions:
import numpy as np
for _ in range(int(input())):
	n = int(input())
	if n < 3:
		print(-1)
	elif n & 1:
		l = np.arange(1, n + 1)
		print(*l)
	else:
		l = np.arange(1, n - 2)
		print(*l, end=' ')
		print(n, n - 2, n - 1)


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(-1)
	elif n % 2:
		for i in range(n, 0, -1):
			print(i, end=' ')
		print()
	else:
		for i in range(1, n - 2):
			print(i, end=' ')
		print(f'{n} {n - 2} {n - 1}')


for tc in range(int(input())):
	n = int(input())
	if n == 2:
		print(-1)
	elif n % 2 == 0:
		ans = [2, 3, 1, 4]
		for i in range(n - 4):
			ans.append(5 + i)
		print(*ans)
	else:
		print(*[i for i in range(1, n + 1)])


vojj = int(input())
for vishnesh in range(vojj):
	n = int(input())
	if n % 2:
		for i in range(1, n + 1):
			print(i, end=' ')
		print()
	elif n == 2:
		print(-1)
	else:
		for i in range(1, n - 2):
			print(i, end=' ')
		print(n, end=' ')
		print(n - 2, end=' ')
		print(n - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 2:
		print(-1)
	elif n % 2 == 0:
		a = [2, 3, 1, 4]
		for i in range(5, n + 1):
			a.append(i)
		print(*a)
	else:
		a = [*range(1, n + 1)]
		print(*a)


t = int(input())
while t != 0:
	n = int(input())
	if n == 2:
		print(-1)
		t = t - 1
		continue
	l = []
	if n % 2 == 1:
		for i in range(1, n + 1):
			l.append(i)
		print(*l)
	else:
		x = 1
		for i in range(0, n):
			l.append(x)
			x = x + 1
		l[0] = 2
		l[1] = 3
		l[2] = 1
		print(*l)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	if n <= 2:
		print(-1)
		continue
	else:
		if n % 2 != 0:
			for i in range(n, 0, -1):
				print(i, end=' ')
		else:
			print('2 3 1 4', end=' ')
			for i in range(1, n - 3):
				print(i + 4, end=' ')
		print()


for i in range(int(input())):
	n = int(input())
	list1 = [2, 3, 1]
	list2 = [3, 2, 1]
	if n == 2:
		print(-1)
	elif n == 3:
		for x in list2:
			print(x, end=' ')
		print('')
	elif n % 2 != 0:
		for x in range(1, n + 1):
			print(x, end=' ')
		print(' ')
	elif n > 3:
		for x in list1:
			print(x, end=' ')
		for x in range(4, n + 1):
			print(x, end=' ')
		print('')


for i in range(int(input())):
	n = int(input())
	if n == 2:
		print(-1)
	elif n & 1 == 1:
		print(*list(range(1, n + 1)))
	elif n & 1 == 0:
		print(2, 3, 1, end=' ')
		print(*list(range(4, n + 1)))


t = int(input())
for i in range(t):
	n = int(input())
	if n == 2:
		print(-1)
	elif n % 2 == 1:
		for i in range(1, n + 1):
			print(i, end=' ')
		print()
	else:
		print('2 3 1 4', end=' ')
		for i in range(1, n - 3):
			print(i + 4, end=' ')
		print()


t = input()
for c in range(0, int(t)):
	n = int(input())
	res = []
	for i in range(n):
		res.append(i + 1)
	if n == 2:
		print(-1)
	elif n % 2 == 0:
		temp = res[-1]
		res[-1] = res[-3]
		res[-3] = temp
		temp = res[-1]
		res[-1] = res[-2]
		res[-2] = temp
		print(*res)
	else:
		print(*res)


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(-1)
	elif n % 2:
		print(*[c for c in range(1, n + 1)])
	else:
		ans = [c for c in range(1, n + 1)]
		temp = ans[-3:]
		temp1 = [temp[2], temp[0], temp[1]]
		print(*list(ans[:-3] + temp1))


from collections import Counter, UserString
mod = lambda n: n % (10 ** 9 + 7)
fc_ = [1]
for i in range(1, 1000001):
	fc_.append(i * fc_[i - 1])
	fc_[i] = mod(fc_[i])

def fact(n):
	return fc_[n]

def printm(n):
	print(mod(n))

def yn(b, caps=False):
	if b:
		returning = 'Yes'
	else:
		returning = 'No'
	if caps:
		return returning.upper()
	return returning

def isPrime(n):
	if n > 1:
		for i in range(2, int(n ** 0.5) + 1):
			if not n % i:
				return False
		else:
			return True
	return True

def decimal(n):
	return int(ans) + int(int(ans) != ans)

class mutableStr(UserString):

	def ins(self, n, s):
		if n < 0:
			self.data = self.data = ''.join(list(self.data)[:n + 1]) + s + ''.join(list(self.data)[n + 1:])
		else:
			self.data = ''.join(list(self.data)[:n]) + s + ''.join(list(self.data)[n:])

	def rem(self, s):
		self.data = self.data.replace(s, '')
alphabetOrd = [97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122]
alphabet = list('abcdefghijklmnopqrstuvwxyz')
r1 = lambda n: range(n)
r2 = lambda n: range(1, n + 1)
alph = lambda s: s.isalpha()
sl = lambda l: list(set(l))
inf = float('inf')
soi = lambda : sorted(input())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
si = lambda : mutableStr(input())
lsi = lambda : list(input())
sepi = lambda : map(int, input().split())
seti = lambda : set(map(int, input().split()))
for t in range(int(input())):
	n = ii()
	if n == 2:
		print(-1)
	elif n & 1 == 1:
		print(*r2(n))
	elif n & 1 == 0:
		print(2, 3, 1, *range(4, n + 1))


for _ in range(int(input())):
	m = int(input())
	if m == 2:
		print(-1)
	else:
		ans = [*range(1, m + 1)]
		if m % 2 == 0:
			(ans[m - 1], ans[m - 2], ans[m - 3]) = (m - 1, m - 2, m)
		print(*ans)


import math
alf = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007

def create_dic(nums):
	dic = dict()
	for i in nums:
		if not i in dic:
			dic[i] = 1
		else:
			dic[i] += 1
	return dic

def subarray_sum_max(nums):
	array = []
	suma_parcial = 0
	max_sum = 0
	index = 0
	se_refresco = True
	for i in range(len(nums)):
		suma_parcial += nums[i]
		if max_sum < suma_parcial:
			if se_refresco:
				array = []
				se_refresco = False
				index = i
			max_sum = suma_parcial
		if suma_parcial < 0:
			suma_parcial = 0
			se_refresco = True
		elif not se_refresco:
			array.append(nums[i])
	return (array, index, max_sum)

def busqueda_binaria(nums, x):
	izq = 0
	der = len(nums) - 1
	while izq <= der:
		medio = int((izq + der) / 2)
		if nums[medio] == x:
			return medio
		elif nums[medio] > x:
			der = medio - 1
		else:
			izq = medio + 1
	return -1

def potencia_binaria(a, n):
	if n == 0:
		return 1
	if n == 1:
		return a
	x = potencia_log_n(a, n // 2) % mod
	if n % 2 == 0:
		return x * x % mod
	return x * x * a % mod

def solve():
	n = int(input())
	if n == 2:
		print(-1)
		return
	if n % 2 != 0:
		arr = [i for i in range(1, n + 1)]
	else:
		arr = [i for i in range(n, 3, -1)]
		arr.append(1)
		arr.append(3)
		arr.append(2)
	print(*arr, sep=' ')
test = int(input())
while test != 0:
	solve()
	test -= 1


for _ in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		print(' '.join([str(i) for i in range(1, n + 1)]))
	elif n == 2:
		print(-1)
	elif n == 4:
		print('1 4 2 3')
	else:
		li = [str(n - 1), str(n), str(n - 3), str(n - 2), str(n - 4)] + [str(i) for i in range(n - 5, 0, -1)]
		print(' '.join(li))


tests = int(input())
for i in range(tests):
	n = int(input())
	ans = []
	if n == 2:
		ans = [-1]
	elif n & 1:
		ans = [i for i in range(n, 0, -1)]
	else:
		ans = [i for i in range(n, 4, -1)]
		ans.extend([4, 1, 3, 2])
	print(*ans)


n = int(input())
while n:
	n -= 1
	N = int(input())
	if N == 2 or N == 1 or N == 0:
		print(-1)
	elif N % 2:
		l = [int(x) for x in range(1, N + 1)]
		print(*l)
	else:
		ans = list(range(N, 3, -1)) + [1, 3, 2]
		print(*ans)


testcases = int(input())
for i in range(testcases):
	n = int(input())
	if n % 2 == 1:
		for i in range(n, 0, -1):
			print(i, end=' ')
		print()
	else:
		if n == 2:
			print(-1)
			continue
		for i in range(n, 3, -1):
			print(i, end=' ')
		print('1 3 2')


def function(N):
	if N < 3:
		return -1
	if N % 2 != 0:
		return ' '.join([str(i) for i in range(1, N + 1)])
	else:
		return ' '.join(['2', '3', '1'] + [str(i) for i in range(4, N + 1)])

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		val = function(N)
		print(val)
main()


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(-1)
		continue
	a = [x + 1 for x in range(n)]
	if n & 1 == 0:
		(a[0], a[1], a[2]) = (a[1], a[2], a[0])
	print(*a)


sl = int(input())
while sl:
	sl -= 1
	n = int(input())
	if n == 2:
		print(-1)
	elif n == 4:
		print(4, 1, 3, 2)
	elif n % 2 == 1:
		for i in range(n):
			print(i + 1, end=' ')
		print()
	else:
		for i in range(n - 4):
			print(n - i, end=' ')
		print(4, 1, 3, 2)


for _ in range(int(input())):
	N = int(input())
	if N == 2:
		print(-1)
	elif N % 2:
		print(*range(1, N + 1))
	else:
		print(2, 3, 1, 4, *range(5, N + 1))


t = int(input())
for i in range(t):
	n = int(input())
	a = []
	for j in range(n):
		a.append(j + 1)
	if n % 2 != 0:
		print(*a)
	elif n <= 2:
		print(-1)
	else:
		a[0] = 2
		a[1] = 3
		a[2] = 1
		print(*a)


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(-1)
	elif n % 2 == 1:
		q = []
		for i in range(1, n + 1):
			q.append(i)
		print(*q)
	else:
		q = []
		for i in range(1, n + 1):
			q.append(i)
		g = q.pop()
		q.insert(1, g)
		print(*q)


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(-1)
	else:
		if n % 2:
			print(*range(1, n + 1))
		else:
			l = list(range(1, n + 1))
			l.insert(1, l.pop())
			print(*l)
		print()


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(-1)
	else:
		if n % 2:
			print(*range(1, n + 1))
		elif n % 4 == 0:
			a = range(1, n // 2 + 1)
			b = range(n, n // 2, -1)
			for i in range(n):
				if i % 2:
					print(a[i // 2], end=' ')
				else:
					print(b[i // 2], end=' ')
		else:
			for i in range(n):
				if i == 0:
					print(1, end=' ')
				elif i == 1:
					print(n, end=' ')
				else:
					print(i, end=' ')
		print()


T = int(input())
for i in range(T):
	n = int(input())
	lst = []
	if n == 2:
		print(-1)
	elif n % 2 != 0:
		for i in range(1, n + 1):
			lst.append(str(i))
	else:
		lst.extend(['2', '3', '1', '4'])
		for i in range(5, n + 1):
			lst.append(str(i))
	print(' '.join(lst))


def inparr():
	tmparr = [int(i) for i in input().split()]
	return tmparr
for _ in range(int(input())):
	N = int(input())
	if N % 2:
		bstr = '1'
		for i in range(2, N + 1):
			bstr += f' {i}'
		print(bstr)
	elif N >= 4:
		bstr = '2 3 1 4'
		for i in range(5, N + 1):
			bstr += f' {i}'
		print(bstr)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	result = [2, 3, 1, 4]
	if n == 2:
		print(-1)
	elif n % 2 == 1:
		print(*[i for i in range(1, n + 1)])
	else:
		for i in range(5, n + 1):
			result.append(i)
		print(*result)


for i in range(int(input())):
	x = int(input())
	if x == 2:
		print(-1)
	elif x % 2 == 1:
		a = [i for i in range(x, 0, -1)]
		print(*a)
	else:
		b = [i for i in range(5, x + 1)]
		c = [2, 3, 1, 4]
		print(*c, end=' ')
		print(*b)


from itertools import permutations

def xor(a, s):
	temp = abs(s[0] - s[1])
	for i in range(1, a - 1):
		temp = temp ^ abs(s[i] - s[i + 1])
	if temp == 0:
		return True
	return False
for _ in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		print(*list(range(n, 0, -1)))
	else:
		flag = [-1]
		perm = permutations(list(range(1, n + 1)))
		for i in perm:
			if xor(n, i):
				flag = list(i)
				break
		print(*flag)


t = int(input())
for i in range(t):
	n = int(input())
	if n == 1 or n == 2:
		print(-1)
	elif n % 2 == 1:
		for i in range(1, n + 1):
			print(i, end=' ')
		print()
	else:
		for i in range(1, n - 2):
			print(i, end=' ')
		print(n, n - 2, n - 1)


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(-1)
	elif n % 2 != 0:
		for i in range(1, n + 1):
			print(i, end=' ')
	else:
		l = [2, 3, 1, 4]
		for i in l:
			print(i, end=' ')
		for i in range(5, n + 1):
			print(i, end=' ')
	print()


p = int(input())
for i in range(p):
	n = int(input())
	if n == 2:
		print('-1')
	elif n == 4:
		print('2 3 1 4')
	elif n % 2 != 0:
		l = []
		for i in range(1, n + 1):
			l.append(i)
		print(*l)
	elif n % 2 == 0:
		l = [2, 3, 1, 4]
		for i in range(5, n + 1):
			l.append(i)
		print(*l)


t = int(input())
for i in range(0, t):
	lst = []
	n = int(input())
	if n == 2:
		print(-1)
		continue
	if n % 2 != 0:
		for k in range(n, 0, -1):
			lst.append(k)
		print(*lst, sep=' ')
	else:
		for j in range(1, n - 2):
			lst.append(j)
		lst.append(n)
		lst.append(n - 2)
		lst.append(n - 1)
		print(*lst, sep=' ')


from itertools import permutations
x = int(input())
for y in range(x):

	def main(l, n):
		main_list = []
		for k in range(n - 1):
			main_list.append(abs(l[k] - l[k + 1]))
		return xorOfArray(main_list, n)

	def xorOfArray(main_list, n):
		xor_arr = 0
		for i in range(n - 1):
			xor_arr = xor_arr ^ main_list[i]
		return xor_arr
	n = int(input())
	if n == 2:
		print(-1)
	else:
		perm = permutations(list(range(1, n + 1)))
		for a in perm:
			ans = main(a, n)
			if ans == 0:
				for j in a:
					print(j, end=' ')
				print()
				break
		else:
			print(-1)


import sys
from math import sqrt, log, ceil, gcd
from random import randint as rd
fun = lambda : map(int, input().split())
for _ in range(int(input())):
	n = int(input())
	lst = []
	if n <= 2:
		lst = [-1]
	elif n & 1:
		lst = [i for i in range(1, n + 1)]
	else:
		lst = [2, 3, 1]
		for i in range(4, n + 1):
			lst.append(i)
	print(*lst)


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		for i in range(1, n + 1):
			print(i, end=' ')
		print()
	else:
		if n == 2:
			print(-1)
			continue
		for i in range(1, n - 2):
			print(i, end=' ')
		a = n
		b = n - 1
		c = n - 2
		print(n, n - 2, n - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 2:
		print(-1)
	elif n % 2:
		arr = [i for i in range(1, n + 1)]
		print(*arr)
	else:
		arr = [i for i in range(1, n + 1)]
		arr[0] = 2
		arr[1] = 3
		arr[2] = 1
		print(*arr)


for i in range(int(input())):
	n = int(input())
	if n == 2:
		print(-1)
	elif n % 2 != 0:
		for i in range(1, n + 1):
			print(i, end=' ')
		print()
	else:
		ll = []
		co = [2, 3, 1, 4]
		if n <= 4:
			ll = co[:n]
		else:
			ll.extend(co)
			for j in range(5, n + 1):
				ll.append(j)
		for k in ll:
			print(k, end=' ')
		print()


for _ in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		temp = list(range(n, 0, -1))
		print(*temp)
	elif n == 2:
		print(-1)
	else:
		li = [2, 3, 1, 4]
		if n == 4:
			print(*li)
		else:
			li += range(5, n + 1)
			print(*li)


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(-1)
	elif n % 2 == 1:
		a = list(range(1, n + 1))
		print(*a)
		continue
	elif n == 4:
		a = [2, 3, 1, 4]
		print(*a)
		continue
	else:
		a = [2, 3, 1, 4]
		b = list(range(5, n + 1))
		a.extend(b)
		print(*a)


n = int(input())
a = []
for i in range(n):
	l = int(input())
	a.append(l)
for i in a:
	if i == 2:
		print(-1)
	elif i % 2:
		print(*list(range(1, i + 1)))
	else:
		n = [i - j for j in range(i)]
		res = n[:-4] + [4, 1, 3, 2]
		print(*res)