Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef recently discovered a function $XOR()$, which computes the XOR of all elements of a sequence:
$$XOR(a_{1..n}) = a_{1} \oplus a_{2} \oplus \dots \oplus a_{n}\,.$$

Chef has a sequence $A$ with size $N$. He generated a new sequence $B$ with size $N^{2}$ using the following formula:
$$B_{iN+j+1} = (A_{i+1} + A_{j+1}) \quad \forall\; 0 ≤ i, j < N\,.$$

Compute the value of $XOR(B)$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer — the answer to the problem.

------  Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$2^{0} ≤ A_{i} < 2^{30}$ for each valid $i$

------  Subtasks ------

Subtask #1 (30 points):
$1 ≤ N ≤ 500$ 
$2^{0} ≤ A_{i} < 2^{10}$ for each valid $i$
                  
Subtask #2 (70 points): $1 ≤ N ≤ 10^{5}$

----- Sample Input 1 ------ 
1
2
1 2
----- Sample Output 1 ------ 
6
----- explanation 1 ------ 
Example case 1: The sequence $B$ is $\{A_{1} + A_{1}, A_{1} + A_{2}, A_{2} + A_{1}, A_{2} + A_{2}\} = \{2, 3, 3, 4\}$. The XOR of its elements is $B_{1} \oplus B_{2} \oplus B_{3} \oplus B_{4} = 6$.

Difficulty: EASY
Tags: Bit manipulation

Constructive algorithms

Mathematics

Ad-hoc
Skill types: Bit manipulation

Starter code:

Solutions:
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	ans = 0
	for i in range(N):
		ans ^= A[i]
	print(2 * ans)


t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	ans = 0
	for i in l:
		ans = ans ^ i
	print(2 * ans)


for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	q = 0
	for i in a:
		q ^= 2 * i
	print(q)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = 0
	for i in a:
		b ^= 2 * i
	print(b)


for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans2 = 0
	for i in a:
		ans2 = ans2 ^ 2 * i
	print(ans2)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in l:
		ans = ans ^ i + i
	print(ans)


t = int(input())
for t in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	ans = 0
	for a in arr:
		ans = ans ^ a + a
	print(ans)


for _ in range(int(input())):
	N = int(input())
	seq = list(map(int, input().split()))
	xor_sum = 0
	for ai in seq:
		xor_sum ^= ai + ai
	print(xor_sum)


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	a = [int(i) for i in input().split()]
	xor = 0
	for i in range(n):
		ans = 2 * a[i]
		xor = xor ^ ans
	print(xor)


for x in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	s = 0
	for x in range(N):
		s ^= A[x] * 2
	print(s)


from bisect import bisect_left, bisect_right
import math
from sys import maxsize
from collections import defaultdict
from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	n = ii()
	l = il()
	c = 0
	for i in l:
		c ^= i
	print(c * 2)


T = int(input())
for index in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	p = 1
	for i in range(n):
		t = A[i] + A[i]
		p = p ^ t
	p = p ^ 1
	print(p)


t = input()
for c in range(0, int(t)):
	n = int(input())
	a = list(map(int, input().split()))
	k = 0
	for m in a:
		k ^= 2 * m
	print(k)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = 0
	for i in a:
		ans = ans ^ 2 * i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = 0
	for m in a:
		k ^= 2 * m
	print(k)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = 0
	for i in l:
		a ^= i
	print(2 * a)


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for j in arr:
		ans ^= j + j
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	xor = 0
	for i in range(n):
		xor = xor ^ 2 * a[i]
	print(xor)


def XORAGN(n, a):
	b = []
	for i in range(n):
		b.append(2 * a[i])
	s = 0
	for i in b:
		s = i ^ s
	print(s)
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	XORAGN(n, a)


t = int(input())
while t:
	n = int(input())
	x = list(map(int, input().split()))
	b = []
	for i in range(0, n):
		b.append(2 * x[i])
	s = 0
	for k in b:
		s = s ^ k
	print(s)
	t = t - 1


t = int(input())
while t:
	n = int(input())
	sum = 0
	a = [int(x) for x in input().split()]
	for x in a:
		sum ^= x + x
	print(sum)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	xor = 0
	for i in l:
		xor ^= i
	print(2 * xor)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	var = arr[0]
	for i in range(1, n):
		var = var ^ arr[i]
	print(int(var) * 2)


def xor(l, n):
	temp = 2 * l[0]
	for i in range(1, n):
		temp = temp ^ 2 * l[i]
	return temp
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(xor(l, n))


def xor(a):
	res = a[0]
	for i in range(1, len(a)):
		res = res ^ a[i]
	return res
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(xor(a) * 2)


n = int(input())
for i in range(n):
	m = int(input())
	a = list(map(int, input().split()))
	x = 0
	for i in range(len(a)):
		x = x ^ a[i] + a[i]
	print(x)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = 0
	for j in l:
		s = s ^ j
	print(s * 2)


for i in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	xor = 0
	l = list(map(lambda x: x * 2, l))
	xor = l[0]
	for i in l[1:]:
		xor ^= i
	print(xor)


for i in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	k = 0
	for i in l1:
		k = k ^ i
	print(k * 2)


for _ in range(int(input())):
	n = input()
	xr = 0
	arr = list(map(int, input().split()))
	for x in range(len(arr)):
		xr = xr ^ arr[x] + arr[x]
	print(xr)


for _ in range(int(input())):
	n = input()
	lst = list(map(int, input().split()))
	xor = 0
	for i in range(len(lst)):
		xor = xor ^ lst[i] + lst[i]
	print(xor)


for t in range(int(input())):
	x = int(input(''))
	a = list(map(int, input().split()))
	xor = 0
	for i in range(len(a)):
		xor = xor ^ a[i] + a[i]
	print(xor)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().strip().split()))[:n]
	h = []
	for i in range(n):
		k = l[i] + l[i]
		h.append(k)
	x = 0
	for i in h:
		x = x ^ i
	print(x)


for item in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	f = 0
	for i in a:
		f = f ^ i
	print(f * 2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = 0
	for i in a:
		d = d ^ i
	print(d * 2)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	g = 0
	for i in l:
		g = g ^ i
	print(g * 2)


def solve(arr):
	res = 0
	for num in arr:
		res ^= 2 * num
	return res

def main():
	for _ in range(int(input())):
		input()
		arr = map(int, input().split())
		print(solve(arr))
main()


n = int(input())
for i in range(n):
	N = int(input())
	l = list(map(int, input().split()))
	final = 0
	for j in l:
		final = final ^ 2 * j
	print(final)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for i in arr:
		ans = ans ^ 2 * i
	print(ans)


total_testcases = int(input())
for testcase in range(total_testcases):
	n = int(input())
	a = list(map(int, input().split()))
	result = 0
	for x in a:
		result ^= 2 * x
	print(result)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	for i in l:
		count ^= 2 * i
	print(count)
	t -= 1


for _ in range(int(input())):
	a = int(input())
	b = [int(i) for i in input().split()]
	ans = 0
	for i in b:
		ans ^= i
	print(ans * 2)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	ans = 0
	for p in x:
		ans ^= p
	print(ans * 2)


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	c1 = 0
	for i in lst:
		c1 ^= i
	print(c1 * 2)


try:
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		a = l[0] * 2
		for i in l[1:]:
			a ^= i * 2
		print(a)
except:
	pass