Chef's last task in his internship requires him to construct 2 permutations, each having length N, such that the [bitwise AND] of each pair of elements at every index is the same.

Formally, if the permutations are A and B, then, the value A_{i} \& B_{i} must be constant over all 1≤ i ≤ N.

Help Chef by providing him 2 such permutations. If it is not possible to construct such permutations, print -1 instead.

A permutation is a sequence of integers from 1 to N of length N containing each number exactly once.

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

- First line will contain T, number of test cases. Then the test cases follow.
- Each test case contains of a single line of input, a single integer N denoting the size of the required permutations.

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

- If there are valid permutations that satisfy the required condition, then:
- In the first line, output N space-separated integers denoting the permutation A.
- In the second line, output N space-separated integers denoting the permutation B.
- If there is no valid pair of permutations, print -1 in a single line. 

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
1
2
3

----- Sample Output 1 ------ 
1
1
1 2
2 1
-1

----- explanation 1 ------ 
Test case $1$: There is only one element in each array and the resultant bitwise AND is $1$. Thus, $A = [1]$ and $B = [1]$.

Test case $2$: Let $A = [1,2]$ and $B = [2,1]$. The resultant bitwise AND of each pair at any index is equal to $0$. So, this is a valid pair of permutations.

Test case $3$: There are $6$ permutations of length $3$. It can be seen that any pair of the $6$ permutations does not satisfy the stated condition.

Difficulty: HARD
Tags: Bit manipulation

Mathematics
Skill types: Bit manipulation

Starter code:

Solutions:
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	N = int(input())
	if N == 1:
		print(1)
		print(1)
		continue
	if N % 2 == 0:
		N_copy = N
		ret = []
		while N > 0:
			l = len(bin(N)) - 2
			start = (1 << l) - 1 - N
			ret += list(range(start, N + 1))
			N = start - 1
		print(*range(N_copy, 0, -1))
		print(*ret)
	else:
		print(-1)


import sys

def get_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	if n == 1:
		print(1)
		print(1)
		continue
	if n % 2 != 0:
		print(-1)
		continue
	a = []
	for i in range(1, n + 1):
		a.append(i)
	b = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		if b[i] != 0:
			continue
		val = bin(i + 1)[2:]
		st = ''
		for j in range(len(val)):
			if val[j] == '0':
				st += '1'
			else:
				st += '0'
		val2 = int(st, 2)
		b[val2 - 1] = i + 1
		b[i] = val2
	print(*a)
	print(*b)


import math
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		print(1)
		continue
	if not n % 2 == 0:
		print(-1)
		continue
	for i in range(1, n + 1):
		print(i, end=' ')
	print()
	arr = [0] * n
	x = int(math.pow(2, math.ceil(math.log2(n))) - 1)
	if x == n - 1:
		arr[n - 1] = n - 1
		arr[n - 2] = n
		n = n - 2
	j = x - n
	while j > 0:
		for i in range(j - 1, n):
			arr[i] = x - i - 1
		n = j - 1
		if n == 0:
			break
		x = int(math.pow(2, math.ceil(math.log2(n))) - 1)
		if x == n - 1:
			arr[n - 1] = n - 1
			arr[n - 2] = n
			n = n - 2
		j = x - n
	print(' '.join(map(str, arr)))


import math
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1, 1, sep='\n')
	elif n & 1 == 1:
		print(-1)
	else:
		print(*list(range(1, n + 1))[::-1])
		s1 = ''
		d = {}
		for i in range(n, 0, -1):
			try:
				s1 += str(d[i]) + ' '
			except:
				c = (1 << int(math.log(i, 2)) + 1) - (i + 1)
				d[c] = i
				s1 += str(c) + ' '
		print(s1)


from collections import defaultdict
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		print(1)
		continue
	x = 1
	while x <= n:
		x *= 2
	if n % 2 == 0:
		d = defaultdict(lambda : 0)
		a = []
		b = []
		for i in range(n, 0, -1):
			a.append(i)
			if d[x - 1 - i] == 0 and x - 1 - i <= n:
				b.append(x - 1 - i)
				d[x - 1 - i] = 1
			else:
				while x > i:
					x = x // 2
				x *= 2
				b.append(x - 1 - i)
				d[x - 1 - i] = 1
		print(*a)
		print(*b)
	else:
		print(-1)


from math import log2
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		for i in range(2):
			print(1)
	elif n % 2:
		print(-1)
	else:
		a = [-1] * n
		(start, end) = (-1, -1)
		(hb, lb, bc) = (0, 0, 0)
		(i, flag) = (n - 1, True)
		while i >= 0:
			if end == -1:
				bc = int(log2(i + 1))
				hb += 1
				end = i
			elif bc == int(log2(i + 1)):
				hb += 1
			else:
				lb += 1
				if hb == lb:
					start = i
					for j in range((end - start + 1) // 2):
						a[start + j] = end - j + 1
						a[end - j] = start + j + 1
					(end, bc, hb, lb) = (-1, 0, 0, 0)
			i -= 1
		if not flag:
			print(-1)
		else:
			print(' '.join(map(str, range(1, n + 1))))
			print(' '.join(map(str, a)))


def f(n):
	x = 1
	while x <= n:
		x <<= 1
	return x - 1
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(1)
		print(1)
	elif n % 2 == 0:
		ar = [False for i in range(f(n) + 1)]
		x = f(n)
		tm = n
		for i in range(n, 0, -1):
			if ar[x - i] or x - i > n:
				x = f(i)
			ar[x - i] = True
			print(x - i, end=' ')
		print()
		for i in range(n, 0, -1):
			print(i, end=' ')
		print()
	else:
		print(-1)


import math

def helper():
	return 0

def solve(n):
	if n == 1:
		return '1\n1'
	elif n & 1:
		return '-1'
	else:
		s = ''
		d = {}
		s1 = ''
		for i in range(n, 0, -1):
			s += '%d ' % i
		for i in range(n, 0, -1):
			try:
				s1 += '%d ' % d[i]
			except:
				val = 2 ** (math.floor(math.log2(i)) + 1) - 1 - i
				d[val] = i
				s1 += '%d ' % val
	return s + '\n' + s1.strip()
for _ in range(int(input())):
	n = int(input())
	print(solve(n))


def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())
from math import log2
from math import ceil

def solve(n):
	if n == 0:
		return ([], [])
	if n == 1:
		return ([1], [1])
	elif n == 2:
		return ([1, 2], [2, 1])
	a = []
	b = []
	high = 2 ** (1 + int(log2(n))) - 1
	(x, y) = solve(high - n - 1)
	for i in range(2 * n - high + 1):
		a.append(n - i)
		b.append(high - n + i)
	a += x
	b += y
	return (a, b)
for T in range(int(input())):
	n = ni()
	if n != 1 and n % 2 == 1:
		print(-1)
		continue
	(x, y) = solve(n)
	print(*x)
	print(*y)


import sys, os.path
if os.path.exists('input.txt'):
	sys.stdout = open('output.txt', 'w')
	sys.stdin = open('input.txt', 'r')

def solve():
	n = int(input())
	if n == 1:
		print(1)
		print(1)
	elif n % 2 != 0:
		print(-1)
		return
	a = [i for i in range(1, n + 1) if i % 2 == 0]
	b = []
	seen = set()
	for val in range(2, n + 1, 2):
		res = 0
		for i in range(32):
			temp = res | 1 << i
			if val & 1 == 0 and temp <= n:
				res = temp
			val = val >> 1
		i = 32
		while res in seen:
			if res & 1:
				res = res & ~(1 << i)
			i -= 1
		seen.add(res)
		b.append(res)
	a.extend(b)
	b.extend(a[:n // 2])
	print(*a)
	print(*b)

def main():
	sys.setrecursionlimit(10 ** 8)
	for _ in range(int(input())):
		solve()
main()


import math

def solve(n):
	if n == 0:
		return ([], [])
	if n == 2:
		return ([1, 2], [2, 1])
	rp = 2 ** int(math.log(n, 2))
	nsp = (n - rp) // 2
	(a, b) = ([rp - 1, rp], [rp, rp - 1])
	cnp = 1
	while cnp <= nsp:
		(k1, k2) = (rp - 2 * cnp, rp + 2 * cnp)
		a.insert(0, k1)
		a.insert(0, k1 - 1)
		a.append(k2 - 1)
		a.append(k2)
		b.insert(0, k2 - 1)
		b.insert(0, k2)
		b.append(k1)
		b.append(k1 - 1)
		cnp += 1
	(pa, pb) = solve(rp - (nsp + 1) * 2)
	pa.extend(a)
	pb.extend(b)
	return (pa, pb)
t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 != 0:
		if n == 1:
			print(1)
			print(1)
		else:
			print(-1)
		continue
	(pa, pb) = solve(n)
	for i in range(n):
		print(pa[i], end=' ')
	print('\r')
	for i in range(n):
		print(pb[i], end=' ')
	print('\r')


import math
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(1)
		print(1)
	elif n % 2 != 0:
		print(-1)
	else:
		matches = {}
		a = list(range(n, 0, -1))
		b = []
		for x in a:
			if x in matches:
				b.append(matches[x])
			else:
				val = x ^ 2 ** (int(math.log2(x)) + 1) - 1
				if val == 0:
					val = 2 ** (int(math.log2(x)) + 1)
				b.append(val)
				matches[x] = val
				matches[val] = x
		print(' '.join([str(e) for e in a]))
		print(' '.join([str(e) for e in b]))


def msb(x):
	p = 1
	while p <= x:
		p <<= 1
	return p
for t in range(int(input())):
	n = int(input())
	if n == 1:
		a = ['1']
		b = a
	else:
		a = []
		b = []
		l = n
		while l > 1:
			p = msb(l) - 1
			r = p >> 1
			for i in range(l, r, -1):
				j = p ^ i
				a.extend([str(i), str(j)])
				b.extend([str(j), str(i)])
			l = l ^ p - 1
	if n > 1 and n % 2:
		print(-1)
	else:
		print(' '.join(a))
		print(' '.join(b))


import collections, math
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		print(1)
	elif n % 2 == 1:
		print(-1)
	else:
		ans = [i for i in range(1, n + 1)]
		print(*ans)
		d = collections.defaultdict(lambda : 0)
		for i in range(n, 0, -1):
			if d[i] == 0:
				p = int(math.log(i, 2)) + 1
				p = 2 ** p - 1
				d[i] = i ^ p
				d[i ^ p] = i
		ans = []
		for i in range(1, n + 1):
			ans.append(d[i])
		print(*ans)


def convert(n):
	ss = bin(n)[2:]
	s = ''
	for i in ss:
		if i == '0':
			s += '1'
		else:
			s += '0'
	if int(s, 2) == 0:
		s = '1' + s
	return int(s, 2)
result = []
MAX = 4294967295

def solve(n):
	A = [i for i in range(1, n + 1)]
	B = [MAX for i in range(n, 0, -1)]
	if n == 1:
		print(1)
		print(1)
	elif n & 1:
		print(-1)
	else:
		s = set()
		for i in range(n - 1, 0, -1):
			if B[i] == MAX:
				g = convert(A[i])
				if g <= n:
					if g not in s:
						B[i] = g
						s.add(g)
					if A[i] not in s:
						B[g - 1] = A[i]
					s.add(A[i])
		res = A[0] & B[0]
		f = True
		for i in range(1, n):
			if A[i] & B[i] != res:
				f = False
		if f:
			print(*A)
			print(*B)
t = int(input())
for _ in range(t):
	n = int(input())
	solve(n)


import sys
from io import BytesIO, IOBase
import os
import math
import collections
T = int(input())
for _ in range(T):
	N = int(input())
	if N == 1:
		print(1)
		print(1)
	elif N % 2:
		print(-1)
	else:
		A = [i for i in range(N + 1)]
		B = [0] * (N + 1)
		j = 1
		while 2 * j <= N:
			j *= 2
		for i in range(N, 0, -1):
			if i < j:
				j //= 2
			C = j - 1 - (i - j)
			B[i] = C
		for i in range(N, 0, -1):
			B[B[i]] = i
		print(*A[1:])
		print(*B[1:])


import math
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		print(1)
		continue
	if n & 1:
		print(-1)
		continue
	a = int(math.log(n + 1, 2))
	if n == 2 ** a:
		print(*[x for x in range(1, n + 1)])
		print(*[x for x in range(n - 2, 0, -1)] + [n, n - 1])
	else:
		(ans1, ans2) = ([], [])
		while n > 0:
			a = int(math.log(n + 1, 2))
			a1 = [x for x in range(2 ** a, n + 1)]
			a2 = [x for x in range(2 ** a - 1, 2 ** a - len(a1) - 1, -1)]
			ans1 += a1 + a2
			ans2 += a2 + a1
			if a2:
				n = a2[-1] - 1
			else:
				break
		print(*ans1)
		print(*ans2)


def is_2_pow(N):
	return N == 1 or '0' not in bin(N - 1)[2:]
for _ in range(int(input())):
	N = int(input())
	if N == 1:
		print(1)
		print(1)
	elif N % 2 == 0:
		N_copy = N
		ret = []
		while N > 0:
			l = len(bin(N)) - 2
			start = (1 << l) - 1 - N
			ret.extend(map(str, range(start, N + 1)))
			N = start - 1
		print(' '.join(map(str, range(N_copy, 0, -1))))
		print(' '.join(ret))
	else:
		print(-1)


from bisect import bisect_left
from re import sub
import re
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
import copy

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
	return prime

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
	ans = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				c += 1
				ans.append(n // i)
			else:
				c += 2
				ans.append(i)
				ans.append(n // i)
		i += 1
	return ans
	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 list(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 subsequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def primeFactors(n):
	d = defaultdict(lambda : 0)
	while n % 2 == 0:
		d[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[int(i)] += 1
			n = n / i
	if n > 2:
		d[int(n)] += 1
	return d

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def count(n):
	ans = 0
	while n:
		ans += n % 10
		n //= 10
	return ans

def lcm(a, b):
	return a * b // math.gcd(a, b)

def check(n):
	c = 0
	while n % 2 == 0:
		n //= 2
		c += 1
	return c

def solve():
	n = int(input())
	if n == 1:
		print(1)
		print(1)
	elif n % 2 == 1:
		print(-1)
	else:
		l = [i for i in range(1, n + 1)]
		k = int('1' * (len(bin(max(l))) - 2), 2)
		temp = []
		d = defaultdict(lambda : 0)
		maxi = max(l)
		for ele in l:
			x = k ^ ele
			while True:
				if d[x] == 0 and x <= maxi:
					break
				else:
					x = int(bin(x)[3:], 2)
			temp.append(x)
			d[x] = 1
		print(*l)
		print(*temp)
for _ in range(int(input())):
	solve()


def counter(n):
	val = 0
	c = 0
	while n:
		if n % 2 == 0:
			val += 2 ** c
		c += 1
		n //= 2
	return val
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
		print(1)
	elif n % 2 == 0:
		dict = [False] * (n + 1)
		a = []
		b = []
		for i in range(n, 0, -1):
			if dict[i] == False:
				c = counter(i)
				dict[c] = True
				dict[i] = True
				a.append(i)
				b.append(c)
				a.append(c)
				b.append(i)
		for i in range(n):
			print(a[i], end=' ')
		print()
		for i in range(n):
			print(b[i], end=' ')
		print()
	else:
		print(-1)


import fileinput
pair = lambda a: 2 ** a.bit_length() - 1 - a

def solve(n):
	if n == 0:
		return []
	else:
		lb = pair(n)
		p1 = [(lb + i, n - i) for i in range(0, n - lb + 1)]
		p2 = solve(lb - 1)
		return p1 + p2
with fileinput.input() as f:
	t = int(f.readline().strip())
	for i in range(t):
		n = int(f.readline().strip())
		if n == 1:
			print(1)
			print(1)
		elif n % 2 == 1:
			print(-1)
		else:
			solution = solve(n)
			s1 = f'{solution[0][0]}'
			s2 = f'{solution[0][1]}'
			for (a, b) in solution[1:]:
				s1 += f' {a}'
				s2 += f' {b}'
			print(s1)
			print(s2)


t = int(input())
for i in range(t):
	n = int(input())
	if n == 1:
		print(1)
		print(1)
		continue
	if n % 2:
		print(-1)
		continue
	a = [0 for i in range(n)]
	b = [0 for i in range(n)]
	kk = 0
	maxi = 1
	while maxi * 2 <= n:
		maxi = maxi * 2
	vis = [-1 for i in range(n + 1)]
	while kk < n:
		curr = maxi
		count = 1
		while curr <= n and vis[curr] == -1:
			a[kk] = curr
			b[kk] = curr - count
			kk += 1
			a[kk] = curr - count
			b[kk] = curr
			kk += 1
			vis[curr] = 1
			vis[curr - count] = 1
			count += 2
			curr += 1
		maxi = maxi // 2
	for i in range(n):
		print(a[i], end=' ')
	print()
	for i in range(n):
		print(b[i], end=' ')
	print()


def setBitNumber(n):
	if n == 0:
		return 0
	msb = 0
	n = int(n / 2)
	while n > 0:
		n = int(n / 2)
		msb += 1
	return 1 << msb

def find(n, a, b):
	temp = setBitNumber(n) + 1
	i = 0
	while temp + i <= n:
		a.append(temp + i)
		b.append(temp - i - 3)
		b.append(temp + i)
		a.append(temp - i - 3)
		i += 1
	a.append(temp - 1)
	b.append(temp - 2)
	a.append(temp - 2)
	b.append(temp - 1)
	x = temp - i - 3
	if x > 0:
		(a, b) = find(x, a, b)
	return (a, b)
for _ in range(int(input())):
	n = int(input())
	a = []
	b = []
	if n % 2 == 0:
		find(n, a, b)
		print(*a, sep=' ')
		print(*b, sep=' ')
	elif n == 1:
		print(1)
		print(1)
	else:
		print(-1)


import sys
input = sys.stdin.readline
M = int(1000000000.0) + 7

def bitflip(x):
	bitx = bin(x)[2:]
	ans = ''
	for i in bitx:
		if i == '0':
			ans += '1'
		else:
			ans += '0'
	return int(ans, 2)

def solve():
	n = int(input())
	if n == 1:
		print(1)
		print(1)
		return
	if n % 2 == 1:
		print(-1)
		return
	print(*range(1, n + 1))
	l = [-1] * (n + 1)
	for i in range(n, 0, -1):
		if l[i] == -1:
			l[i] = bitflip(i)
			l[bitflip(i)] = i
	print(*l[1:])
for _ in range(int(input())):
	solve()


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		if n == 1:
			print(1)
			print(1)
		elif n & 1:
			print(-1)
		else:
			print(*[i for i in range(1, n + 1)])
			B = []
			num = n
			while len(B) < num:
				p = 1
				while p <= n:
					p <<= 1
				p -= 1
				for i in range(n, -1, -1):
					if ~i & p > n:
						n = i
						break
					B.append(~i & p)
			print(*B[::-1])
except:
	pass