Chef has an array A of length N. He can perform the following operation on A: 

1) Select an index i (1 ≤ i ≤ N - 1) and select an integer X (1 ≤ X < 2^{20}). \\
2) Set A_{i} := (A_{i} \oplus X) and A_{i + 1} := (A_{i + 1} \oplus X). (Here, \oplus denotes the [bitwise XOR operation]

Determine if Chef can make all the elements of A equal by applying the above operation any number of times (possibly zero).

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

- The first line contains a single integer 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 array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

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

For each test case, output YES if it is possible to make all the elements of A equal by applying the given operation any number of times. Otherwise, output NO.

You may print each character of YES and NO in uppercase or lowercase (for example, yes, yEs, Yes will be considered identical).

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$0 ≤A_{i} < 2^{20}$
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

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

----- Sample Output 1 ------ 
YES
NO
YES

----- explanation 1 ------ 
Test Case 1: We can apply the following operation:
- $[3, 2, 2, 3] \xrightarrow{i = 2, X = 1} [3, 3, 3, 3]$

Test Case 2: It can be proved that we can not make all the elements of $A$ equal by applying the given operation.

Test Case 3: We can apply the following operations:
- $[1, 2, 4] \xrightarrow{i = 1, X = 6} [7, 4, 4] \xrightarrow{i = 2, X = 3} [7, 7, 7]$

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics


Solutions:
for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	x = a[0]
	for i in a[1:]:
		x ^= i
	if x == 0 or n & 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	sum1 = 0
	list1 = [int(x) for x in input().split()]
	if n % 2 != 0:
		print('YES')
	else:
		for j in range(n):
			sum1 = sum1 ^ list1[j]
		if sum1 == 0:
			print('YES')
		else:
			print('NO')


tc = int(input())
for _ in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	if n % 2 == 1:
		print('YES')
	else:
		d = 0
		for i in range(n):
			d = d ^ a[i]
		if d == 0:
			print('YES')
		else:
			print('NO')


case = int(input())
for _ in range(case):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	res = 0
	i = 0
	while i < n:
		res ^= arr[i]
		i += 1
	if n & 1 == 0:
		if res == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	arr = input().split()
	ans = 0
	for i in arr:
		ans ^= int(i)
	if n & 1:
		ans = 0
	print('YES') if ans == 0 else print('NO')


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	ans = 0
	if n % 2 == 1:
		print('YES')
		continue
	for i in a:
		ans ^= i
	if ans != 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	x = 0
	if a & 1:
		print('YES')
	else:
		for i in b:
			x = x ^ i
		if x == 0:
			print('YES')
		else:
			print('NO')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n % 2 == 1:
		print('YES')
	else:
		c = 0
		for i in a:
			c ^= i
		if c == 0:
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for i in arr:
		ans = ans ^ i
	for i in range(n - 1):
		if arr[i] != ans:
			d = ans ^ arr[i]
			arr[i] = ans
			arr[i + 1] = arr[i + 1] ^ d
	if arr.count(ans) == n:
		print('YES')
	else:
		print('NO')


from functools import reduce

def isUnique(arr: list) -> bool:
	return len(set(arr)) == 1
T = int(input())
for _ in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	for i in range(1, n):
		arr[i] = arr[i] ^ arr[i - 1]
		arr[i - 1] = 0
	if arr[-1] == 0:
		print('YES')
	elif n & 1:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	m = int(input())
	l = [int(j) for j in input().split()]
	r = l[0]
	for j in range(1, len(l)):
		r = r ^ l[j]
	if r == 0:
		print('YES')
	elif len(l) % 2 == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = 0
	for i in range(n):
		x = x ^ a[i]
	if n % 2 != 0:
		print('YES')
	elif x == 0:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	l = int(input())
	li = [int(x) for x in input().split()]
	xor = 0
	for x in li:
		xor = xor ^ x
	if xor == 0:
		print('YES')
	elif l % 2 != 0:
		print('YES')
	else:
		print('NO')


import sys
for i in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	xor = 0
	for i in range(n):
		xor ^= ar[i]
	if xor == 0 and n % 2 == 0 or n % 2:
		print('YES')
	else:
		print('NO')


def soln(n, arr):
	cur = 0
	for i in arr:
		cur ^= i
	if cur == 0:
		return 'YES'
	return 'YES' if n & 1 else 'NO'
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(soln(n, arr))


vojj = int(input())
for vishnesh in range(vojj):
	n = int(input())
	arr = list(map(int, input().split()))
	a0 = []
	a1 = []
	for i in range(19, -1, -1):
		c0 = 0
		c1 = 0
		for j in arr:
			if j >> i & 1:
				c1 = c1 + 1
			else:
				c0 = c0 + 1
		a0.append(c0)
		a1.append(c1)
	p = 0
	for i in range(20):
		if a0[i] % 2 == 0 or a1[i] % 2 == 0:
			p = p + 1
		else:
			break
	if p == 20:
		print('YES')
	else:
		print('NO')


import sys
from math import gcd, sqrt, log, ceil, floor
tc = int(input().strip())
for t in range(tc):
	n = int(input())
	arr = list(map(int, input().split()))
	if n % 2 == 1:
		print('YES')
	else:
		arrXor = arr[0]
		for i in arr[1:]:
			arrXor ^= i
		if arrXor == 0:
			print('YES')
		else:
			print('NO')


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007

def solve(num, nums):
	xor = 0
	for i in nums:
		xor ^= i
	if num % 2 == 1:
		return 'YES'
	else:
		if xor == 0:
			return 'YES'
		return 'NO'
tried = int(input())
for _ in range(tried):
	num = inp()
	nums = seq()
	print(solve(num, nums))


for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	if n % 2 == 1:
		print('YES')
	else:
		for i in range(n - 1):
			(num[i], num[i + 1]) = (num[i] ^ num[i], num[i + 1] ^ num[i])
		if num[-1]:
			print('NO')
		else:
			print('YES')


def inparr():
	tmparr = [int(i) for i in input().split()]
	return tmparr
for _ in range(int(input())):
	N = int(input())
	arr = inparr()
	res = 0
	for i in arr:
		res ^= i
	if len(arr) % 2:
		print('YES')
	else:
		print('YES') if res == 0 else print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	if n % 2 == 1:
		print('YES')
	else:
		x = 0
		for i in ar:
			x = x ^ i
		if x == 0:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if len(arr) % 2 == 1:
		print('YES')
	else:
		x = 0
		for i in arr:
			x = x ^ i
		if x == 0:
			print('YES')
		else:
			print('NO')


from operator import xor
from functools import reduce
n = int(input())
for i in range(n):
	leng = int(input())
	ins = list(map(int, input().split(' ')))
	if leng % 2 != 0:
		print('YES')
	else:
		ins = reduce(xor, ins)
		if ins == 0:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	res = 0
	for i in range(n):
		res = a[i] ^ res
	if n % 2 != 0:
		print('YES')
	elif res == 0:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	r = 0
	for i in a:
		r = r ^ i
	if n % 2 == 1 or r == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = 0
	for i in arr:
		res ^= i
	if not res or n % 2 == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	x = 0
	for i in arr:
		x ^= i
	if x == 0 or n % 2 != 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = 0
	for j in l:
		x ^= j
	if x == 0 or n % 2 != 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	x = a[0]
	if n % 2 == 0:
		for j in range(0, n - 1):
			x = x ^ a[j + 1]
		if x == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

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

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

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	N = inp()
	A = inlt()
	an = 'YES'
	if not N % 2:
		x = 0
		for a in A:
			x ^= a
		if x:
			an = 'NO'
	ans.append(an)
outplt(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

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

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

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	N = inp()
	A = [bin(x)[2:].rjust(20, '0') for x in inlt()]
	B = [sum((int(a[i]) for a in A)) for i in range(20)]
	an = 'YES'
	for b in B:
		if b < N and b % 2 and (N % 2 == 0):
			an = 'NO'
			break
	ans.append(an)
outplt(ans)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	if n % 2 == 0:
		res = 0
		for item in arr:
			res = res ^ item
		if res == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


def ans(arr):
	for i in range(0, len(arr) - 1):
		t = arr[i]
		arr[i] = 0
		arr[i + 1] ^= t
	if arr.count(0) == len(arr):
		return 'YES'
	else:
		if (len(arr) - 1) % 2 == 0:
			return 'YES'
		return 'NO'
test_cases = int(input())
while test_cases != 0:
	d = input()
	d2 = list(map(int, input().split()))
	print(ans(d2))
	test_cases -= 1


def solve(n, l):
	r = 0
	for i in l:
		r = r ^ i
	if r == 0:
		return 'YES'
	if n % 2 != 0:
		return 'YES'
	return 'NO'
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(solve(n, l))


n = int(input())
for i in range(n):
	k = int(input())
	m = list(map(int, input().split()))
	if k % 2 == 0:
		for i in range(k - 1):
			if m[i] != 0:
				m[i + 1] ^= m[i]
				m[i] = 0
		if sum(m) == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


t = int(input())
for x in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	ma = max(a)
	bma = bin(ma)
	lmba = len(bma)
	d0 = [0 for x in range(lmba)]
	d1 = [0 for x in range(lmba)]
	ba = [list(bin(ai)) for ai in a]
	for (i, ai) in enumerate(ba):
		lai = len(ai)
		for j in range(lmba - lai):
			ba[i].insert(2, '0')
	for ai in ba:
		for (i, c) in enumerate(ai):
			if i >= 2:
				if c == '0':
					d0[i] += 1
				else:
					d1[i] += 1
	if all((d0[i] % 2 == 0 or d1[i] % 2 == 0 for i in range(2, lmba))):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = 0
	for i in l:
		a = a ^ i
	if a == 0:
		print('YES')
	elif n & 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	xor = 0
	for i in l:
		xor ^= i
	if len(l) % 2 == 1 or xor == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t != 0:
	n = int(input())
	arr = list(map(int, input().split()))
	k = arr[0]
	for i in range(1, len(arr)):
		k ^= arr[i]
	if k == 0:
		print('YES')
	elif n & 1:
		print('YES')
	else:
		print('NO')
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	r = l[0]
	for j in range(1, len(l)):
		r ^= l[j]
	if r == 0:
		print('YES')
	elif n & 1:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split(' ')))
	x = 0
	for a in arr:
		x ^= a
	if n % 2:
		print('YES')
	elif n % 2 == 0 and x > 0:
		print('NO')
	else:
		print('YES')
	t -= 1


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n & 1:
		print('YES')
	else:
		xor = 0
		for i in l:
			xor = xor ^ i
		if xor == 0:
			print('YES')
		else:
			print('NO')


testcases = int(input())
for eachcase in range(testcases):
	length = int(input())
	array = list(map(int, input().split()))
	if length & 1:
		print('YES')
	else:
		orops = array[0]
		for nums in range(1, length):
			orops = orops ^ array[nums]
		if orops == 0:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n % 2 != 0:
		print('YES')
	else:
		res = 0
		for i in l:
			res = res ^ i
		if res == 0:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = l[0]
	for i in range(1, n):
		k ^= l[i]
	if k == 0:
		print('YES')
	elif len(l) % 2 == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(1, n):
		a[i] ^= a[i - 1]
		a[i - 1] = 0
	if a[n - 1] == 0 or n % 2 == 1:
		print('YES')
	else:
		print('NO')


from functools import *
t = int(input())
try:
	while t > 0:
		n = int(input())
		l = list(map(int, input().split()))
		if n % 2 == 1:
			print('YES')
		elif reduce(lambda x, y: x ^ y, l) == 0:
			print('YES')
		else:
			print('NO')
		t -= 1
except:
	print('')


test_case = int(input())
for i in range(test_case):
	N = int(input())
	A = list(map(int, input().split()))
	xor = 0
	for i in range(N):
		xor ^= A[i]
	if N % 2 == 1 or xor == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	list = [int(i) for i in input().split()]
	xor = 0
	ans = False
	if n % 2 == 0:
		for i in list:
			xor ^= i
		if xor == 0:
			ans = True
		else:
			ans = False
	else:
		ans = True
	if ans == True:
		print('YES')
	else:
		print('NO')


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	for x in range(n - 1):
		l[x + 1] ^= l[x]
	if n % 2:
		print('YES')
	elif l[n - 1] == 0:
		print('YES')
	else:
		print('NO')