You are given arrays A and B with N non-negative integers each.

An array X of length N is called *good*, if:
All elements of the array X are non-negative;
X_{1} | X_{2} | \ldots | X_{i} = A_{i} for all (1≤ i≤ N);
X_{i} \& X_{(i+1)} \& \ldots \& X_{N} = B_{i} for all (1≤ i≤ N).

Find the maximum bitwise XOR of all elements over all good arrays X.  
More formally, find the maximum value of X_{1}\oplus X_{2}\oplus \ldots X_{N}, over all good arrays X.  
It is guaranteed that at least one such array X exists.

Note that |, \&, and \oplus denote the bitwise [or], [and], and [xor] operations respectively.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains one integer N — the size of the array.
- The next line contains N space-separated integers describing the elements of the array A. 
- The next line contains N space-separated integers describing the elements of the array B. 

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

For each test case, output on a new line, the maximum bitwise XOR of all elements over all good arrays X.  

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} < 2^{30}$
$0 ≤ B_{i} < 2^{30}$
- It is guaranteed that at least one such array $X$ exists.
- Sum of $N$ over all test cases is less than $3\cdot 10^{5}$.

----- Sample Input 1 ------ 
2
3
0 3 3
0 2 2
2
2 3
0 1

----- Sample Output 1 ------ 
1
3
----- explanation 1 ------ 
Test case $1$: An optimal *good* array is $X = [0, 3, 2]$.
- For $i = 1$: $A_{1} = X_{1} = 0$ and $B_{1} = X_{1}$ $\&$ $X_{2}$ $\&$ $X_{3} = 0$.
- For $i = 2$: $A_{2} = X_{1}$ $|$ $X_{2} = 3$ and $B_{2} = X_{2}$ $\&$ $X_{3} = 2$.
- For $i = 3$: $A_{3} = X_{1}$ $|$ $X_{2}$ $|$ $X_{3} = 3$ and $B_{3} = X_{3} = 2$.

The XOR of all elements of $X$ is $0\oplus 3\oplus 2 = 1$. It can be proven that this is the maximum XOR value for any $X$.

Test case $2$: An optimal *good* array is $X = [2, 1]$.
- For $i = 1$: $A_{1} = X_{1} = 2$ and $B_{1} = X_{1}$ $\&$ $X_{2} = 0$.
- For $i = 2$: $A_{2} = X_{1}$ $|$ $X_{2} = 3$ and $B_{2} = X_{2} = 1$.

The XOR of all elements of $X$ is $2\oplus 1 = 3$. It can be proven that this is the maximum XOR value for any $X$.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Mathematics


Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	first = [-1] * 31
	last = [n] * 31
	for i in range(n):
		for j in range(31):
			if a[i] & 1 << j and first[j] == -1:
				first[j] = i
			if b[i] & 1 << j and last[j] == n:
				last[j] = i
	res = 0
	for i in range(31):
		(L, R) = (first[i], last[i])
		if L == -1:
			continue
		if L == R:
			if (n - R) % 2:
				res += 2 ** i
		elif L + 2 == R:
			if (n - R) % 2 == 0:
				res += 2 ** i
		else:
			res += 2 ** i
	print(res)


import math
from collections import defaultdict
from itertools import accumulate
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	(s, e) = ([n] * 31, [-1] * 31)
	(l, r) = (0, (1 << 31) - 1)
	for i in range(n):
		c = l ^ a[i]
		binary = bin(c)[2:].rjust(31)
		for j in range(31):
			if binary[j] == '1':
				assert s[j] == n
				s[j] = i
		l = a[i]
		c = r ^ b[n - 1 - i]
		binary = bin(c)[2:].rjust(31)
		for j in range(31):
			if binary[j] == '1':
				assert e[j] == -1
				e[j] = n - 1 - i
		r = b[n - 1 - i]
	ans = ''
	for i in range(31):
		assert s[i] != e[i]
		if s[i] < e[i] - 1:
			ans += '1'
		else:
			ones = n - 1 - e[i]
			ones += 1 if s[i] < e[i] else 0
			ans += str(ones & 1)
	print(int(ans, 2))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	first_1 = [-1] * 31
	last_1 = [n] * 31
	for i in range(n):
		for bit in range(30):
			if a[i] & 1 << bit and first_1[bit] == -1:
				first_1[bit] = i
			if b[i] & 1 << bit and last_1[bit] == n:
				last_1[bit] = i
	ans = 0
	for i in range(31):
		(L, R) = (first_1[i], last_1[i])
		if L == -1:
			continue
		if L == R:
			if (n - R) % 2:
				ans += 2 ** i
		elif L + 2 == R:
			if (n - R) % 2 == 0:
				ans += 2 ** i
		else:
			ans += 2 ** i
	print(ans)


import functools
import operator

def LII():
	return [int(x) for x in input().split()]

def II():
	return int(input())
for _ in range(int(input())):
	n = II()
	a = LII()
	b = LII()
	sets = [a[0] | b[0]] + [x & ~y | z for (x, y, z) in zip(a[1:], a[:-1], b[1:])]
	resets = [~x & y | ~z for (x, y, z) in zip(b[:-1], b[1:], a[:-1])] + [~a[-1] | ~b[-1]]
	xor_sets = functools.reduce(operator.xor, sets, 0)
	arbs = functools.reduce(operator.or_, (~x & ~y for (x, y) in zip(sets, resets)), 0)
	print(arbs | xor_sets)


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

def li():
	return list(mi())

def si():
	return str(input())

def lsi():
	return si().strip().split(' ')

def ni():
	return int(input())
import sys
input = sys.stdin.readline
for _ in range(ni()):
	n = ni()
	a = li()
	b = li()
	first_1 = [-1] * 31
	last_1 = [n] * 31
	for i in range(n):
		for bit in range(30):
			if a[i] & 1 << bit and first_1[bit] == -1:
				first_1[bit] = i
			if b[i] & 1 << bit and last_1[bit] == n:
				last_1[bit] = i
	ans = 0
	for i in range(31):
		(L, R) = (first_1[i], last_1[i])
		if L == -1:
			continue
		if L == R:
			if (n - R) % 2:
				ans += 2 ** i
		elif L + 2 == R:
			if (n - R) % 2 == 0:
				ans += 2 ** i
		else:
			ans += 2 ** i
	print(ans)


def check_bit(n, a, b, bit):
	required = 0
	possible = False
	for i in range(n):
		must_be_0 = must_be_1 = False
		ai = a[i] >> bit & 1
		must_be_0 = must_be_0 or ai == 0
		if i > 0:
			aim1 = a[i - 1] >> bit & 1
			must_be_1 = must_be_1 or (aim1 == 0 and ai == 1)
		else:
			must_be_1 = must_be_1 or ai == 1
		bi = b[i] >> bit & 1
		must_be_1 = must_be_1 or bi == 1
		if i + 1 < n:
			bip1 = b[i + 1] >> bit & 1
			must_be_0 = must_be_0 or (bip1 == 1 and bi == 0)
		else:
			must_be_0 = must_be_0 or bi == 0
		if must_be_1:
			required += 1
		if not must_be_1 and (not must_be_0):
			possible = True
	return required & 1 == 1 or possible

def solve(n, a, b):
	answer = 0
	for bit in range(30):
		if check_bit(n, a, b, bit):
			answer |= 1 << bit
	return answer
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(solve(n, a, b))


def read_int():
	return int(input())

def read_ints():
	return [int(x) for x in input().split()]

def read_case():
	n = read_int()
	a = read_ints()
	b = read_ints()
	return (n, a, b)

def solve(n, a, b):
	x = 0
	bit = 1
	while bit <= 2 ** 30:
		first_1 = 0
		while first_1 < len(a) and a[first_1] & bit == 0:
			first_1 += 1
		if first_1 == len(a):
			bit *= 2
			continue
		last_0 = len(b) - 1
		while last_0 >= 0 and b[last_0] & bit != 0:
			last_0 -= 1
		if last_0 > first_1 + 1:
			x |= bit
		elif last_0 == first_1 + 1:
			if (len(b) - last_0) % 2 == 1:
				x |= bit
		elif (len(b) - first_1) % 2 == 1:
			x |= bit
		bit *= 2
	return x
cases = read_int()
for case in range(cases):
	print(solve(*read_case()))