Chef has an array A of length N. 

Chef wants to append a non-negative integer X to the array A such that the [bitwise OR] of the entire array becomes = Y i.e. (A_{1} \ | \ A_{2} \ | \  \ldots \ | \ A_{N} \ | \ X) = Y. (Here, | denotes the bitwise OR operation)

Determine the minimum possible value of X. If no possible value of X exists, output -1.

------ 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 two integers N and Y — the size of the array A and final bitwise OR 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 the minimum possible value of X for which (A_{1} \ | \ A_{2} \ | \  \ldots \ | \ A_{N} \ | \ X) = Y holds.

If no such value exists, output -1.

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

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

----- Sample Input 1 ------ 
4
4 15
3 5 6 2
3 8
1 2 1
1 1
0
5 7
1 2 4 2 1

----- Sample Output 1 ------ 
8
-1
1
0

----- explanation 1 ------ 
Test Case 1: $(3 \ | \ 5 \ | \ 6 \ | \ 2 \ | \ X) = 15$ holds for the following values of $X$: $\{8, 9, 10, 11, 12, 13, 14, 15\}$. The minimum among them is $8$. 

Test Case 2: It can be proven that no valid value of $X$ exists.

Test Case 3: $(0 \ | \ X) = 1$ holds for only $X = 1$.

Source: codechef | Difficulty: EASY
Tags: Bit manipulation

Mathematics


Solutions:
T = int(input())
for _ in range(T):
	(N, Y) = input().split()
	arr = list(map(int, input().split()))
	Y = int(Y)
	x = 0
	for i in arr:
		x = x | i
	a = x & Y
	if x == a:
		print(a ^ Y)
	else:
		print(-1)


def valadd(l, s):
	s = int(s)
	r = 0
	for i in l:
		r = r | i
		if r > s:
			return -1
	val = r ^ s
	if r | val == s:
		return val
	return -1
ans = []
n = int(input())
for i in range(n):
	a = input()
	a = a.split(' ')
	res = input()
	res = list(map(int, res.split(' ')))
	ans.append(valadd(res, a[1]))
for x in ans:
	print(x)


t = int(input())
for i in range(t):
	a = 0
	N = list(map(int, input().split()))
	v = list(map(int, input().split()))
	for j in range(len(v)):
		a = a | v[j]
	count = N[1] - a
	if count & N[1] == count:
		print(count)
	else:
		print(-1)


t = int(input())
for t in range(t):
	l = list(map(int, input().split()))
	y = l[1]
	l2 = list(map(int, input().split()))
	m = 0
	for i in range(len(l2)):
		m = l2[i] | m
	count = y - m
	if count & y == count:
		print(count)
	else:
		print(-1)


t = int(input())
for i in range(t):
	(N, Y) = map(int, input().split())
	A = list(map(int, input().split()))
	xor = 0
	for i in A:
		xor = xor | i
	AA = xor ^ Y
	if AA | xor == Y:
		print(AA)
	else:
		print(-1)


tests = int(input())
for i in range(tests):
	st1 = map(int, input().split())
	(N, Y) = list(st1)
	st2 = map(int, input().split())
	arr = list(st2)
	bit_or = 0
	check = -1
	for ele in arr:
		bit_or = bit_or | ele
	ele_poss = bit_or ^ Y
	if ele_poss | bit_or == Y:
		print(ele_poss)
	else:
		print(-1)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	for i in range(0, a):
		c = c | l[i]
	d = c ^ b
	if d | c == b:
		print(d)
	else:
		print(-1)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	g = 0
	for i in l:
		g = g | i
	ans = g ^ b
	if ans | g == b:
		print(ans)
	else:
		print(-1)


def main():
	for _ in range(int(input())):
		(n, y) = map(int, input().split())
		arr = list(map(int, input().split()))
		orr = 0
		for i in arr:
			orr |= i
		req = orr ^ y
		if req | orr == y:
			print(req)
		else:
			print(-1)
main()


for i in range(int(input())):
	(n, y) = map(int, input().split())
	a = list(map(int, input().split()))
	orp = a[0]
	found = 0
	for i in range(n - 1):
		orp = orp | a[i + 1]
	req = orp ^ y
	if req | orp == y:
		print(req)
	else:
		print(-1)


t = int(input())
for i in range(t):
	(n, y) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = []
	x = 0
	for j in l:
		x |= j
	req = x ^ y
	if req | x == y:
		print(req)
	else:
		print(-1)


for _ in range(int(input())):
	(n, y) = map(int, input().split())
	arr = list(map(int, input().split()))
	a = 0
	for i in arr:
		a = a | i
	x = a ^ y
	if a | x == y:
		print(x)
	else:
		print('-1')


T = int(input())
while T > 0:
	(N, Y) = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	sum = 0
	for j in A:
		sum = j | sum
	if sum ^ Y | sum == Y:
		print(sum ^ Y)
	else:
		print(-1)
	T -= 1


import functools
for _ in range(int(input())):
	(n, y) = map(int, input().split())
	lst = list(map(int, input().split()))
	x = 0
	res = functools.reduce(lambda x, y: x | y, lst)
	if y - res | res == y:
		print(y - res)
	else:
		print(-1)


for i in range(int(input())):

	def dtob(bit):
		bin = 0
		mul = 1
		while bit > 0:
			bin += mul * (bit % 2)
			bit //= 2
			mul *= 10
		return bin
	(n, y) = map(int, input().split())
	a = list(map(int, input().split()))
	bit = 0
	for j in range(n):
		bit = bit | a[j]
	bin_a = dtob(bit)
	bin_y = dtob(y)
	flag = 1
	z = []
	while bin_a != 0 or bin_y != 0:
		if bin_a % 10 == 1 and bin_y % 10 == 0:
			flag = 0
			print(-1)
			break
		elif bin_a % 10 == 0 and bin_y % 10 == 1:
			z.append(1)
		elif bin_a % 10 == 1 and bin_y % 10 == 1:
			z.append(0)
		elif bin_a % 10 == 0 and bin_y % 10 == 0:
			z.append(0)
		bin_a //= 10
		bin_y //= 10
	if flag == 1:
		mul = 1
		val = 0
		for k in range(len(z)):
			val += z[k] * mul
			mul *= 2
		print(val)


t = int(input())
for i in range(t):
	(n, y) = (int(x) for x in input().split())
	arr = list(map(int, input().strip().split()))[:n]
	bor = 0
	for i in arr:
		bor = bor | i
	if bor > y:
		print(-1)
		continue
	elif bor == y:
		print(0)
		continue
	else:
		bin_bor_list = [int(x) for x in str(bin(bor))[2:]]
		bin_y_list = [int(x) for x in str(bin(y))[2:]]
		(a, b) = (len(bin_y_list), len(bin_bor_list))
		if a > b:
			for i in range(a - b):
				bin_bor_list.insert(0, 0)
		bin_x_list = []
		for i in range(a):
			if bin_bor_list[i] == bin_y_list[i]:
				bin_x_list.append(0)
			elif bin_bor_list[i] == 1 and bin_y_list[i] == 0:
				print(-1)
				break
			else:
				bin_x_list.append(1)
		if bin_bor_list[i] == 1 and bin_y_list[i] == 0:
			continue
		bin_x_list = bin_x_list[::-1]
		x = 0
		for i in range(len(bin_x_list)):
			x = x + bin_x_list[i] * pow(2, i)
		print(x)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	x = list(map(int, input().split()))
	k = 0
	for j in range(n):
		k |= x[j]
	s1 = list(bin(k)[2:])
	s2 = list(bin(m)[2:])
	flag = True
	res = []
	if len(s1) > len(s2):
		print(-1)
	else:
		a = len(s2) - len(s1)
		s1 = ['0'] * a + s1
		for i in range(len(s2) - 1, -1, -1):
			if s2[i] == '0':
				if s1[i] == '1':
					print(-1)
					flag = False
					break
				else:
					res.append('0')
			elif s1[i] == '1':
				res.append('0')
			else:
				res.append('1')
		if flag == True:
			res = res[::-1]
			res = ''.join(res)
			print(int(res, 2))


for _ in range(int(input())):
	(N, Y) = map(int, input().split())
	A = list(map(int, input().split()))
	X = Y
	B = 0
	for i in A:
		X &= ~i
		B |= i
	print(X if X | B == Y else -1)


t = int(input())
for i in range(t):
	(n, y) = map(int, input().split())
	a = list(map(int, input().split()))
	x = 0
	for i in a:
		x = x | i
	res = x ^ y
	if x | res == y:
		print(res)
	else:
		print(-1)


for i in range(int(input())):
	(n, y) = map(int, input().split())
	a = list(map(int, input().split()))
	result = a[0]
	for i in range(n):
		result |= a[i]
	result = y - result
	ans = result & y
	if ans == result:
		print(ans)
	else:
		print(-1)


for i in range(int(input())):
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	s = 0
	for j in range(a[0]):
		s |= b[j]
	if s ^ a[1] | a[1] == a[1]:
		print(s ^ a[1])
	else:
		print('-1')


for _ in range(int(input())):
	(n, y) = map(int, input().split())
	l = list(map(int, input().split()))
	res = l[0]
	for i in range(1, len(l)):
		res = res | l[i]
	if res == y:
		print(0)
	else:
		t = y - res
		if res | t == y:
			print(t)
		else:
			print(-1)


for _ in range(int(input())):
	(n, y) = map(int, input().split())
	A = list(map(int, input().split()))
	orr = 0
	for i in A:
		orr = orr | i
	x = orr ^ y
	if orr | x == y:
		print(x)
	else:
		print('-1')


for i in range(int(input())):
	(_, q) = list(map(int, input().split()))
	n = input().split()
	a = int(n[0])
	for i in range(1, len(n)):
		a = a | int(n[i])
	q = bin(q)[2:]
	a = bin(a)[2:]
	maxl = max(len(a), len(q))
	q = q.rjust(maxl, '0')
	a = a.rjust(maxl, '0')
	res = ''
	f = 0
	for i in range(maxl - 1, -1, -1):
		if a[i] == '0':
			if q[i] == '0':
				res += '0'
			else:
				res += '1'
		elif q[i] == '0':
			print(-1)
			f = 1
			break
		else:
			res += '0'
	if not f:
		print(int(res[::-1], 2))


from operator import or_
from functools import reduce
from itertools import zip_longest
trials = int(input())
for i in range(trials):
	(_, result) = [int(x) for x in input().split()]
	inputs = [int(x) for x in input().split()]
	partial = reduce(or_, inputs)
	partial_bits = bin(partial)[2:]
	result_bits = bin(result)[2:]
	x = ''
	for (r, p) in zip_longest(reversed(result_bits), reversed(partial_bits), fillvalue='0'):
		if r == p:
			x += '0'
		elif r == '0':
			break
		else:
			x += '1'
	else:
		x = x[::-1]
		x = eval('0b' + x)
		print(x)
		continue
	print('-1')


for i in range(int(input())):
	(n, y) = list(map(int, input().split()))
	l1 = list(map(int, input().split()))
	s = 0
	for j in range(n):
		s |= l1[j]
	x = s ^ y
	p = s | x
	if p == y:
		print(x)
	else:
		print(-1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	o = 0
	for i in range(n):
		o |= l[i]
	j = o ^ m
	p = o | j
	if p == m:
		print(j)
	else:
		print(-1)


t = int(input())
for i in range(t):
	(n, y) = map(int, input().split())
	a = list(map(int, input().split()))
	f = 0
	for j in range(n):
		f = f | a[j]
	k = y - f
	if k & y == k:
		print(k)
	else:
		print('-1')


t = int(input())
while t:
	t -= 1
	(n, y) = map(int, input().split())
	arr = list(map(int, input().split()))
	op = 0
	for i in arr:
		op |= i
	res = op ^ y
	if op | res == y:
		print(res)
	else:
		print(-1)


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	s = list(map(int, input().split()))
	p = 0
	for i in s:
		p = p | i
	q = b - p
	if q & b == q:
		print(q)
	else:
		print(-1)


for i in range(int(input())):
	(n, y) = map(int, input().split())
	l = list(map(int, input().split()))
	p = 0
	for i in l:
		p = p | i
	q = y - p
	if q & y == q:
		print(q)
	else:
		print(-1)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	n = 0
	for i in l:
		n = n | i
	o = b - n
	if o & b == o:
		print(o)
	else:
		print(-1)


for _ in range(int(input())):
	(n, y) = list(map(int, input().split()))
	x = list(map(int, input().split()))
	t = 0
	for i in x:
		t |= i
	test = False
	bin_t = bin(t)[2:]
	bin_y = bin(y)[2:]
	if len(bin_t) < len(bin_y):
		bin_t = '0' * (len(bin_y) - len(bin_t)) + bin_t
	flag = False
	new = ''
	for (i, e) in zip(bin_t, bin_y):
		if i == '1' and e == '0':
			flag = True
		elif i == '0' and e == '1':
			new += '1'
		else:
			new += '0'
	if flag:
		print(-1)
	else:
		new = '0b' + new
		if t | int(new, 2) == y:
			print(int(new, 2))
		else:
			print(-1)


T = int(input())
for i in range(T):
	(N, Y) = map(int, input().split())
	A = list(map(int, input().split()))
	res = A[0]
	result = 0
	for i in A[1:]:
		res |= i
	val = res ^ Y
	if val | res == Y:
		print(val)
	else:
		print(-1)


def min_possible_value_of_x(n, y, a):
	or_sum = 0
	for i in range(n):
		or_sum |= a[i]
	if or_sum == y:
		return 0
	if y > or_sum:
		return y - or_sum if y & ~or_sum == y - or_sum else -1
	return -1
t = int(input())
for _ in range(t):
	(n, y) = map(int, input().split())
	a = list(map(int, input().split()))
	x = min_possible_value_of_x(n, y, a)
	print(x)


for T in range(int(input())):
	line = list(map(int, input().split()))
	(N, Y) = (line[0], line[1])
	A = list(map(int, input().split()))
	b_or = A[0]
	for value in A[1:]:
		b_or |= value
	val = b_or ^ Y
	if val | b_or == Y:
		print(val)
	else:
		print(-1)


from functools import reduce
for _ in range(int(input())):
	(n, y) = map(int, input().split())
	arr = list(map(int, input().split()))
	old = reduce(lambda a, b: a | b, arr)
	num = y ^ old
	if int(num | old) != y:
		print(-1)
	else:
		print(num)


T = int(input())
for i in range(T):
	(N, Y) = map(int, input().split())
	nums = list(map(int, input().split()))
	x1 = 0
	for i in nums:
		x1 = x1 | i
	res = Y ^ x1
	if res | x1 == Y:
		print(res)
	else:
		print(-1)


for _ in range(int(input())):
	(n, y) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))[:n]
	allOr = 0
	for i in arr:
		allOr = allOr | i
	found = False
	power = 1
	ans = 0
	while y != 0:
		temp1 = y & 1
		temp2 = allOr & 1
		if temp1 == 1:
			ans += power * (temp2 ^ 1)
		elif temp2 == 1:
			found = True
			break
		power = power * 2
		y = y >> 1
		allOr = allOr >> 1
	if found or allOr != 0:
		print(-1)
	else:
		print(ans)


t = int(input())
for i in range(t):
	(n, y) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	orr = 0
	for i in arr:
		orr |= i
	temp = orr ^ y
	if temp | orr == y:
		print(temp)
	else:
		print(-1)


t = int(input())
for i in range(t):
	(a, x) = map(int, input().split())
	l = list(map(int, input().split()))
	temp = 0
	for i in l:
		temp = temp | i
	new = temp ^ x
	if temp | new == x:
		print(new)
	else:
		print('-1')


T = int(input())
for i in range(T):
	(N, Y) = map(int, input().split())
	A = list(map(int, input().split()))
	temp = 0
	for i in A:
		temp = temp | i
	new = temp ^ Y
	if temp | new == Y:
		print(new)
	else:
		print('-1')


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	poss_value = 0
	xor = 0
	lst = list(map(int, input().split()))
	for x in lst:
		xor = xor | x
	z = xor ^ b
	if xor | z == b:
		print(z)
	else:
		print('-1')


t = int(input())
for i in range(t):
	flag = 0
	(n, y) = map(int, input().split())
	temp = input()
	val = 0
	for i in temp.split():
		val = val | int(i)
	val = val ^ y
	if val | y != y:
		print(-1)
	else:
		print(val)


T = int(input())
for i in range(T):
	(N, Y) = map(int, input().split())
	L = list(map(int, input().split()))
	p = 0
	for j in L:
		p = p | j
	t = Y ^ p
	if p | t == Y:
		print(t)
	else:
		print(-1)


for i in range(int(input())):
	(n, y) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 0
	for i in range(0, n):
		s = s | l[i]
	r = s ^ y
	if r | s == y:
		print(r)
	else:
		print('-1')


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	for i in a:
		s = s | i
	s1 = int(bin(s ^ x), 2)
	if s1 | s == x:
		print(s1)
	else:
		print(-1)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	z = list(map(int, input().split()))
	b = 0
	for m in range(len(z)):
		b = b | z[m]
	p = b ^ y
	if p | b == y:
		print(p)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	(n, y) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 0
	for i in l:
		s |= i
	p = s ^ y
	if p | s != y:
		print(-1)
	else:
		print(s ^ y)