JJ had an array A of length N such that 0 ≤ A_{i} < 2^{30} for all 1 ≤ i ≤ N.  
He listed down the [XOR] of all the [subsequences] of A of size ≥ (N - 1) in some random order. Let's call the XOR of these (N + 1) subsequences as B_{1}, B_{2}, \ldots, B_{N+1}.

Unfortunately, he lost the initial array A. Can you help him recover it?

If there are multiple arrays which satisfy the given conditions, print any. Also, it is guaranteed that corresponding to the given input, an answer always exists.

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

- The first line will contain T - the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N - the size of the initial array A.
- The second line of each test case contains (N + 1) integers B_{1}, B_{2}, \ldots, B_{N+1} - the XOR of all the subsequences of A of size ≥ (N - 1) in some random order.

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

For each test case, output N integers A_{1}, A_{2}, \ldots, A_{N} which satisfy the given conditions.

If multiple answers exist, print any.

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

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

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

Subtask 1 (40 points):
$N$ is odd
Subtask 2 (60 points):
Original constraints.

----- Sample Input 1 ------ 
2
3
2 3 0 1
5
27 15 23 30 29 31

----- Sample Output 1 ------ 
1 2 3
1 2 4 8 16

----- explanation 1 ------ 
Let $\oplus$ denote the [bitwise XOR operation].

- Test Case 1: $A = [1, 2, 3]$ satisfies all the conditions since $[2, 3, 0, 1] = [1 \oplus 3, 1 \oplus 2, 1 \oplus 2 \oplus 3, 2 \oplus 3]$

- Test Case 2: $A = [1, 2, 4, 8, 16]$ satisfies all the conditions since $[27, 15, 23, 30, 29, 31] = 
[1 \oplus 2 \oplus 8 \oplus 16, 1 \oplus 2 \oplus 4 \oplus 8, 1 \oplus 2 \oplus 4 \oplus 16, 2 \oplus 4 \oplus 8 \oplus 16, 1 \oplus 4 \oplus 8 \oplus 16, 1 \oplus 2 \oplus 4 \oplus 8 \oplus 16]$

----- Sample Input 2 ------ 
2
2
1 0 1
4
5 3 1 4 3

----- Sample Output 2 ------ 
1 1
5 4 2 2

----- explanation 2 ------ 
Note: The above test case belongs to subtask 2.

Let $\oplus$ denote the [bitwise XOR operation].

- Test Case 1: $A = [1, 1]$ satisfies all the conditions since $[1, 0, 1] = [1, 1 \oplus 1, 1]$

- Test Case 2: $A = [5, 4, 2, 2]$ satisfies all the conditions since $[5, 3, 1, 4, 3] = [5 \oplus 2 \oplus 2, 5 \oplus 4 \oplus 2, 5 \oplus 4 \oplus 2 \oplus 2, 4 \oplus 2 \oplus 2, 5 \oplus 4 \oplus 2]$

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics


Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	if n % 2 != 0:
		X = 0
		for i in nums:
			X ^= i
		nums.remove(X)
		A = list(map(lambda a: a ^ X, nums))
		A.sort()
	else:
		X = min(nums)
		nums.remove(X)
		A = [a ^ X for a in nums]
		A.sort(reverse=True)
	print(*A)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = [int(i) for i in input().split()]
	if n % 2 == 0:
		m = min(arr)
		arr.pop(arr.index(m))
		arr = [i ^ m for i in arr]
		print(*arr)
	else:
		d = 0
		for i in arr:
			d ^= i
		arr.pop(arr.index(d))
		arr = [i ^ d for i in arr]
		print(*arr)


import sys
from itertools import islice
from functools import reduce
from operator import xor
for s in islice(sys.stdin, 2, None, 2):
	(*b,) = map(int, s.split())
	x = reduce(xor, b) or min(b)
	if x:
		for i in range(len(b)):
			b[i] ^= x
	b.remove(0)
	print(*b)


t = int(input())
for _ in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	if n % 2:
		xor = 0
		for el in b:
			xor = xor ^ el
	else:
		xor = min(b)
	(a, f) = ([], False)
	for el in b:
		if el != xor or f:
			a += [~xor & el | ~el & xor]
		else:
			f = True
	print(' '.join(map(str, a)))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n % 2 != 0:
		tm = 0
		for ele in arr:
			tm = tm ^ ele
		ans = []
		for ele in arr:
			if ele != tm:
				ans.append(ele ^ tm)
		while len(ans) < n:
			ans.append(0)
		for ele in ans:
			print(ele, end=' ')
		print()
	else:
		tm = 0
		arr.sort()
		if 1 == 1:
			for i in range(1, n + 1):
				print(arr[i] ^ arr[0], end=' ')
			print()