You are given non-negative integers A, B and C.

Does there exist a non-negative integer X such that A \oplus X+ B \oplus X = C \oplus X?

As a reminder, \oplus denotes the [bitwise XOR operation].

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- The only line of each test case contains three space-separated non-negative integers A, B and C.

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

For each test case, print on a new line the answer: YES if valid X exists, and NO otherwise.

Each character of the output may be printed in either uppercase or lowercase, i.e, the strings Yes, YES, yes, yEs will all be treated as identical.

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

$1 ≤ T ≤ 10^{5}$
$0 ≤ A, B, C < 2^{27}$

----- Sample Input 1 ------ 
5
2 5 7
2 3 13
7 0 7
2 7 6
1 6 6

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

----- explanation 1 ------ 
Test case $1$: $X=0$ satisfies the equation.

Test case $2$: It can be proved that there does not exist a non-negative integer $X$ which satisfies the equation.

Test case $3$: $X=0$ satisfies the equation.

Test case $4$: $X=3$ satisfies the equation.

Test case $5$: $X=1$ satisfies the equation.

Difficulty: HARD
Tags: Bit manipulation

Constructive algorithms

Mathematics

Ad-hoc
Skill types: Bit manipulation

Starter code:

Solutions:
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	(a, b, c) = (bin(a)[2:], bin(b)[2:], bin(c)[2:])
	m = max(len(a), len(b), len(c))
	a = '0' * (m - len(a)) + a
	b = '0' * (m - len(b)) + b
	c = '0' * (m - len(c)) + c
	f = 0
	ans = True
	for i in range(m):
		if a[i] + b[i] + c[i] == '001' or a[i] + b[i] + c[i] == '110':
			f += 1
	if f % 2 == 1:
		ans = False
	if ans:
		print('YES')
		continue
	print('NO')


def bit_gen(x):
	l = [0 for _ in range(27)]
	for i in range(1, 28):
		l[-i] = x % 2
		x = x // 2
	return l
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	(a, b, c) = (bin(a)[2:], bin(b)[2:], bin(c)[2:])
	m = max(len(a), len(b), len(c))
	a = '0' * (m - len(a)) + a
	b = '0' * (m - len(b)) + b
	c = '0' * (m - len(c)) + c
	f = 0
	ans = True
	for i in range(1, m + 1):
		if a[-i] + b[-i] + c[-i] == '001' or a[-i] + b[-i] + c[-i] == '110':
			f = not f
	if not f:
		print('YES')
		continue
	print('NO')


def ans(a, b, c):
	x = ''
	carry = 0
	for i in range(0, len(bin(max(a, b, c))) - 2):
		ai = a >> i & 1
		bi = b >> i & 1
		ci = c >> i & 1
		if ai == bi == ci == 1:
			if carry == 0:
				x += '1'
			else:
				x += '0'
		elif ai == bi == ci == 0:
			if carry == 0:
				x += '0'
			else:
				x += '1'
		elif ai != bi and ci == 0:
			if carry == 0:
				x += '1'
			else:
				x += '0'
		elif ai != bi and ci == 1:
			if carry == 0:
				x += '0'
			else:
				x += '1'
		elif ai == bi == 1 and ci == 0:
			if carry == 0:
				carry = 1
				x += '0'
			else:
				x += '1'
				carry = 0
		elif carry == 0:
			x += '1'
			carry = 1
		else:
			carry = 0
			x += '0'
	x = x[::-1]
	x = int(x, 2)
	if (a ^ x) + (b ^ x) == c ^ x:
		return 'YES'
	return 'NO'
test_cases = int(input())
while test_cases != 0:
	d = list(map(int, input().split()))
	print(ans(d[0], d[1], d[2]))
	test_cases -= 1


def bit_gen(x):
	l = [0 for _ in range(27)]
	for i in range(1, 28):
		l[-i] = x % 2
		x = x // 2
	return l
t = int(input())
for _ in range(t):
	(a, b, c) = map(int, input().split())
	carry = 0
	a_ = bit_gen(a)
	b_ = bit_gen(b)
	c_ = bit_gen(c)
	for i in range(1, 28):
		if a_[-i] == 0 and b_[-i] == 0 and (c_[-i] == 1) or (a_[-i] == 1 and b_[-i] == 1 and (c_[-i] == 0)):
			carry = not carry
	if carry == 1:
		print('NO')
	else:
		print('YES')


from functools import lru_cache

@lru_cache()
def f(a, b, c, x, t):
	if a == 0 and b == 0 and (c == 0):
		return t == 0
	p = (a % 2 ^ x) + (x ^ b % 2) + t
	if p % 2 != c % 2 ^ x:
		return False
	return f(a >> 1, b >> 1, c >> 1, 0, p > 1) or f(a >> 1, b >> 1, c >> 1, 1, p > 1)
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	print('YES' if f(a, b, c, 0, 0) or f(a, b, c, 1, 0) else 'NO')


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	carry = 0
	for i in range(30):
		v1 = a >> i & 1
		v2 = b >> i & 1
		v3 = c >> i & 1
		for x in range(2):
			if (v1 ^ x) + (v2 ^ x) + carry & 1 == v3 ^ x:
				carry = int((v1 ^ x) + (v2 ^ x) + carry > 1)
				break
	if carry:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	(a, b, c) = map(int, input().split())
	count = 0
	for i in range(28):
		x = a >> i & 1
		y = b >> i & 1
		z = c >> i & 1
		if x == y and y != z:
			count += 1
		if i > a and i > b and (i > c):
			break
	if count % 2 == 0:
		print('YES')
	else:
		print('NO')


def getBitSum(a, b, carry):
	return a ^ b ^ carry

def getCarry(a, b, carry):
	return (a & b) + (carry & (a ^ b))

def getIthBit(x, i):
	return x >> i & 1
t = int(input())
while t:
	t -= 1
	(a, b, c) = map(int, input().split())
	result = 0
	possibleSum = 0
	possibleSumWithXor = 0
	carry = 0
	(ai, bi, ci) = (0, 0, 0)
	(aix, bix, cix) = (0, 0, 0)
	for i in range(27):
		ai = getIthBit(a, i)
		bi = getIthBit(b, i)
		ci = getIthBit(c, i)
		possibleSum = getBitSum(ai ^ 0, bi ^ 0, carry)
		aix = ai ^ 1
		bix = bi ^ 1
		cix = ci ^ 1
		possibleSumWithXor = getBitSum(aix, bix, carry)
		if possibleSum == ci:
			carry = getCarry(ai, bi, carry)
		elif possibleSumWithXor == cix:
			carry = getCarry(aix, bix, carry)
			result = result | 1 << i
		else:
			break
	if carry == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	carry = 0
	for bits in range(28):
		x = a >> bits & 1
		y = b >> bits & 1
		z = c >> bits & 1
		if x == y and y != z:
			carry += 1
		if bits > a and bits > b and (bits > c):
			break
	if carry % 2 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(a, b, c) = list(map(int, input().split()))
	ba = bin(a)[2:]
	bb = bin(b)[2:]
	bc = bin(c)[2:]
	m = max(len(ba), len(bb), len(bc))
	ba = '0' * (m - len(ba)) + ba
	bb = '0' * (m - len(bb)) + bb
	bc = '0' * (m - len(bc)) + bc
	ba = ba[::-1]
	bb = bb[::-1]
	bc = bc[::-1]
	c = 0
	for i in range(len(ba)):
		ua = int(ba[i])
		ub = int(bb[i])
		uc = int(bc[i])
		f = c + ua + ub
		r = f % 2
		c = f // 2
		if r != uc:
			ua = (ua + 1) % 2
			ub = (ub + 1) % 2
			uc = (uc + 1) % 2
			f = c + ua + ub
			c = f // 2
	if c == 1:
		ans = 'NO'
	else:
		ans = 'YES'
	print(ans)


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	carry = 0
	for i in range(30):
		(x, y, z) = (a >> i & 1, b >> i & 1, c >> i & 1)
		carry ^= x == y and y != z
	print('YES' if not carry else 'NO')


import sys, threading
import math
from os import path
from collections import deque, defaultdict
from bisect import *
from string import ascii_lowercase
from functools import cmp_to_key
from random import randint
import heapq

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline
MAXN = 1123456

class mydict:

	def __init__(self, func=lambda : 0):
		self.random = randint(0, 1 << 32)
		self.default = func
		self.dict = {}

	def __getitem__(self, key):
		mykey = self.random ^ key
		if mykey not in self.dict:
			self.dict[mykey] = self.default()
		return self.dict[mykey]

	def get(self, key, default):
		mykey = self.random ^ key
		if mykey not in self.dict:
			return default
		return self.dict[mykey]

	def __setitem__(self, key, item):
		mykey = self.random ^ key
		self.dict[mykey] = item

	def getkeys(self):
		return [self.random ^ i for i in self.dict]

	def values(self):
		var = []
		for i in self.dict:
			var.append(self.dict[i])
		return var

	def __str__(self):
		return f'{[(self.random ^ i, self.dict[i]) for i in self.dict]}'

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

def mod(n):
	return n % (1000000000 + 7)

def solve(t):
	(a, b, c) = readInts()
	carry = False
	for i in range(30):
		ba = a & 1 << i
		bb = b & 1 << i
		bc = c & 1 << i
		if ba != bb:
			continue
		else:
			if bc == ba == bb:
				continue
			if carry:
				carry = False
			else:
				carry = True
	if carry:
		print('NO')
	else:
		print('YES')

def main():
	t = 1
	if path.exists('F:/Comp Programming/input.txt'):
		sys.stdin = open('F:/Comp Programming/input.txt', 'r')
		sys.stdout = open('F:/Comp Programming/output1.txt', 'w')
	t = readInts()
	for i in range(t):
		solve(i + 1)
main()


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	carry = 0
	for bit in range(32):
		(x, y, z) = (a >> bit & 1, b >> bit & 1, c >> bit & 1)
		if x == y and y != z:
			carry ^= 1
	print(['YES', 'NO'][carry])


from sys import stdin
input = stdin.readline
MAX = 30

def solve(A, B, C):
	carry = 0
	for bit in range(MAX):
		a = A >> bit & 1
		b = B >> bit & 1
		c = C >> bit & 1
		if (a, b, c) in [(0, 0, 1), (1, 1, 0)]:
			carry = 1 - carry
	if carry == 0:
		return 'YES'
	else:
		return 'NO'
T = int(input().strip())
for problem in range(1, T + 1):
	(A, B, C) = [int(x) for x in input().strip().split()]
	print(solve(A, B, C))


def s(a, b, c):
	r = 0
	for i in range(28):
		(x, y, z) = (a >> i & 1, b >> i & 1, c >> i & 1)
		if x == y and y != z:
			r ^= 1
	return r
t = int(input())
for i in range(t):
	(a, b, c) = map(int, input().split())
	p = s(a, b, c)
	if p:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	i = 0
	con = 0
	while i < 28:
		x = a & 1
		y = b & 1
		z = c & 1
		if x == y and x != z:
			con = con + 1
		i = i + 1
		a = a >> 1
		b = b >> 1
		c = c >> 1
	if con % 2:
		print('NO')
	else:
		print('YES')


def soln(a, b, c):

	def form(s):
		return '0' * (32 - len(s)) + s
	a = form(bin(a)[2:])
	b = form(bin(b)[2:])
	c = form(bin(c)[2:])
	count = 0
	for i in range(31, 0, -1):
		if a[i] == b[i] and a[i] != c[i]:
			count += 1
	return 'YES' if not count & 1 else 'NO'
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	print(soln(a, b, c))


def solve(a, b, c):
	carry = 0
	for i in range(28):
		if a & 1 == b & 1 and b & 1 != c & 1:
			carry ^= 1
		a >>= 1
		b >>= 1
		c >>= 1
	if carry:
		return False
	return True
t = int(input())
for _ in range(t):
	(a, b, c) = [int(x) for x in input().split()]
	ans = solve(a, b, c)
	if ans:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(A, B, C) = map(int, input().split())
	CARRY = 0
	for BIT in range(28):
		(X, Y, Z) = (A >> BIT & 1, B >> BIT & 1, C >> BIT & 1)
		if X == Y and Y != Z:
			CARRY ^= 1
	print('NO' if CARRY else 'YES')


def get_bin(n):
	l = [0 for _ in range(28)]
	for i in range(1, 28):
		l[-i] = n % 2
		n //= 2
	return l
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	(a1, b1, c1) = (get_bin(a), get_bin(b), get_bin(c))
	car = 0
	for i in range(1, 28):
		if a1[-i] == b1[-i] and c1[-i] != b1[-i]:
			car = not car
	if car:
		print('NO')
	else:
		print('YES')


t = int(input())
while t:
	(a, b, c) = map(int, input().split())
	k = 0
	for i in range(28):
		(x, y, z) = (a >> i & 1, b >> i & 1, c >> i & 1)
		if x == y and y != z:
			k ^= 1
	if k:
		print('NO')
	else:
		print('YES')
	t -= 1


import sys
sys.setrecursionlimit(10 ** 8)
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	p = 1
	cnt = 0
	for i in range(30):
		if a & p == 0 and b & p == 0 and (c & p != 0) or (a & p != 0 and b & p != 0 and (c & p == 0)):
			cnt += 1
		p *= 2
	if cnt % 2 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(a, b, c) = map(int, input().split())
	bina = str(bin(a))[2:]
	binb = str(bin(b))[2:]
	binc = str(bin(c))[2:]
	lena = len(bina)
	lenb = len(binb)
	lenc = len(binc)
	n = max([lena, lenb, lenc])
	bina = (n - lena) * '0' + bina
	binb = (n - lenb) * '0' + binb
	binc = (n - lenc) * '0' + binc
	bina = bina[::-1]
	binb = binb[::-1]
	binc = binc[::-1]
	carry = 0
	for i in range(n):
		if carry == 0:
			if bina[i] == binb[i] and binb[i] == binc[i] or bina[i] != binb[i]:
				continue
			else:
				carry = 1
		elif bina[i] == binb[i] and bina[i] != binc[i]:
			carry = 0
			continue
		elif bina[i] == binb[i] and binb[i] == binc[i]:
			continue
		elif bina[i] != binb[i]:
			continue
	if carry == 0:
		print('YES')
	else:
		print('NO')


def has_ans(a, b, c, s):
	if a == 0 and b == 0 and (c == 0):
		return s == 0
	next_bit = 0
	if ((next_bit ^ a) + (next_bit ^ b)) % 2 != ((c ^ next_bit) + s) % 2:
		next_bit = 1
	s += -(a % 2 ^ next_bit) - (b % 2 ^ next_bit) + (c % 2 ^ next_bit)
	s /= 2
	return has_ans(int(a / 2), int(b / 2), int(c / 2), s)
t = int(input())
for t0 in range(t):
	(a, b, c) = list(map(int, input().split()))
	if has_ans(a, b, c, 0):
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(a, b, c) = map(int, input().split())
	p = 1
	cnt = 0
	for i in range(30):
		if a & p == 0 and b & p == 0 and (c & p != 0) or (a & p != 0 and b & p != 0 and (c & p == 0)):
			cnt += 1
		p *= 2
	if cnt % 2 == 0:
		print('YES')
	else:
		print('NO')


import sys, bisect
input = sys.stdin.readline
for _ in range(int(input())):
	(x, y, z) = map(int, input().split())
	a = '{:027b}'.format(x)
	b = '{:027b}'.format(y)
	c = '{:027b}'.format(z)
	ca = 0
	for i in range(26, -1, -1):
		x = int(a[i]) + int(b[i]) + ca
		t = ca
		ca = (x - x % 2) // 2
		if x % 2 == int(c[i]):
			continue
		elif a[i] == '1' and b[i] == '1' and (c[i] == '1'):
			ca -= 1
		elif a[i] == '0' and b[i] == '0' and (c[i] == '1'):
			ca += 1
		elif a[i] == '0' and b[i] == '0' and (c[i] == '0'):
			ca += 1
		elif a[i] == '1' and b[i] == '1' and (c[i] == '0'):
			ca -= 1
		else:
			continue
	if ca == 0:
		print('YES')
	else:
		print('NO')


t = int(input())

def possible(a, b, c, carry):
	if a + b + c == 0:
		return carry == 0
	ax = a % 2
	bx = b % 2
	cx = c % 2
	if (ax + bx + carry) % 2 == cx:
		if possible(a >> 1, b >> 1, c >> 1, (ax + bx + carry) // 2):
			return True
	if (1 - ax + 1 - bx + carry) % 2 == 1 - cx:
		if possible(a >> 1, b >> 1, c >> 1, (1 - ax + 1 - bx + carry) // 2):
			return True
	return False
for _ in range(t):
	(a, b, c) = map(int, input().split())
	print('YES' if possible(a, b, c, 0) else 'NO')


from collections import *
from itertools import *
from functools import *
from heapq import *
import sys, math
input = sys.stdin.readline
for _ in range(int(input())):
	(a, b, c) = list(map(int, input().split()))
	a1 = '{0:b}'.format(a)
	b1 = '{0:b}'.format(b)
	c1 = '{0:b}'.format(c)
	a1 = a1[::-1]
	b1 = b1[::-1]
	c1 = c1[::-1]
	a1 += '0' * (33 - len(a1))
	b1 += '0' * (33 - len(b1))
	c1 += '0' * (33 - len(c1))
	crr = 0
	for x in range(33):
		if a1[x] != b1[x]:
			continue
		elif a1[x] == c1[x]:
			continue
		else:
			crr = 1 - crr
	if crr:
		print('NO')
	else:
		print('YES')