You are given two arrays $a$ and $b$, consisting of $n$ integers each.

Let's define a function $f(a, b)$ as follows:

let's define an array $c$ of size $n$, where $c_i = a_i \oplus b_i$ ($\oplus$ denotes bitwise XOR);

the value of the function is $c_1 \mathbin{\&} c_2 \mathbin{\&} \cdots \mathbin{\&} c_n$ (i.e. bitwise AND of the entire array $c$).

Find the maximum value of the function $f(a, b)$ if you can reorder the array $b$ in an arbitrary way (leaving the initial order is also an option).


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the size of arrays $a$ and $b$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i < 2^{30}$).

The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i < 2^{30}$).

The sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case print one integer — the maximum value of the function $f(a, b)$ if you can reorder the array $b$ in an arbitrary way.


-----Examples-----

Input
3
5
1 0 0 3 3
2 3 2 1 0
3
1 1 1
0 0 3
8
0 1 2 3 4 5 6 7
7 6 5 4 3 2 1 0
Output
2
0
7


-----Note-----

None

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Graph traversal

Sorting

Greedy algorithms

Divide and conquer


Solutions:
import sys
from collections import defaultdict

def input():
	return sys.stdin.readline().rstrip()

def main():
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	res = 0
	bit = max(max(A), max(B)).bit_length()

	def check(res):
		cnt = defaultdict(int)
		for x in A:
			cnt[x & res] += 1
		for x in B:
			cnt[~x & res] -= 1
		return all((v == 0 for v in cnt.values()))
	for i in range(bit - 1, -1, -1):
		if check(res | 1 << i):
			res |= 1 << i
	print(res)
t = int(input())
for _ in range(t):
	main()


import sys
from collections import defaultdict
input = sys.stdin.readline

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))

	def check(pre):
		cnt = defaultdict(int)
		for x in a:
			x &= pre
			cnt[x] += 1
		for x in b:
			x &= pre
			x ^= pre
			cnt[x] -= 1
			if cnt[x] == 0:
				del cnt[x]
		return len(cnt.keys()) == 0
	ans = 0
	for j in range(29, -1, -1):
		ans |= 1 << j
		if check(ans) is False:
			ans ^= 1 << j
	print(ans)
for _ in range(int(input())):
	solve()


from collections import Counter
m = int(input())

def solve(n: int, a: list, b: list) -> None:
	ans = 0
	for digit in range(29, -1, -1):
		t = ans | 1 << digit
		cnt_a = Counter((x & t for x in a))
		cnt_b = Counter((x & t for x in b))
		flag = True
		for x in cnt_a.keys():
			if cnt_a[x] != cnt_b[x ^ t]:
				flag = False
				break
		if flag:
			ans = t
	print(ans)
while m > 0:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	solve(n, a, b)
	m -= 1


import collections

def do(val, a, b):
	d = collections.defaultdict(lambda : 0)
	for i in range(len(a)):
		d[val ^ val & a[i]] += 1
		d[val & b[i]] -= 1
	for i in d.keys():
		if d[i] != 0:
			return False
	return True
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = 0
	for i in range(30, -1, -1):
		ck = 2 ** i | ans
		if do(ck, a, b):
			ans = ck
	print(ans)


from collections import Counter
MAX_BIT = 32
MASK = []
for i in range(MAX_BIT):
	v = 1 << i
	MASK.append(v)

def solve(n, A, B):
	idx = MAX_BIT - 1
	mask = 0
	while idx >= 0:
		temp = mask | MASK[idx]
		if Counter([temp & x for x in A]) == Counter([temp & ~x for x in B]):
			mask = temp
		idx -= 1
	return mask
N = int(input())
for _ in range(N):
	n = int(input())
	A = [int(x) for x in input().split(' ')]
	B = [int(x) for x in input().split(' ')]
	ans = solve(n, A, B)
	print(ans)


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	b = list(map(int, inp().split()))
	ans = 0
	bit = 1 << 29
	while bit > 0:
		now = ans | bit
		if sorted((i & now for i in a)) == sorted((~i & now for i in b)):
			ans = now
		bit >>= 1
	print(ans)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


for _ in range(int(input())):
	n = int(input())
	r = list(map(int, input().split()))
	j = list(map(int, input().split()))
	ans = 0
	bit = 1 << 29
	while bit > 0:
		now = ans | bit
		if sorted((i & now for i in r)) == sorted((~i & now for i in j)):
			ans = now
		bit >>= 1
	print(ans)


numSamples = int(input())
for _ in range(numSamples):
	_ = input()
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = 0
	mask = 1 << 29
	while mask > 0:
		now = ans | mask
		if sorted([now & i for i in a]) == sorted([now & ~i for i in b]):
			ans = now
		mask >>= 1
	print(ans)


def solve():
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	b = list(map(int, input().strip().split()))
	ans = 0
	bit = 1 << 29
	while bit > 0:
		now = ans | bit
		if sorted((i & now for i in a)) == sorted((~i & now for i in b)):
			ans = now
		bit >>= 1
	print(ans)
t = int(input().strip())
for _ in range(t):
	solve()


def fun(ans, a, b, n):
	a1 = []
	b1 = []
	for i in range(n):
		a1.append(ans & a[i])
		b1.append(ans & b[i] ^ ans)
	a1.sort()
	b1.sort()
	for i in range(n):
		if a1[i] != b1[i]:
			return False
	return True
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	a.sort()
	b.sort()
	ans = 0
	for i in range(30, -1, -1):
		if fun(ans | 2 ** i, a, b, n):
			ans = ans | 2 ** i
	print(ans)


T = int(input())
for t in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a = sorted(a)
	b = sorted(b)[::-1]
	mxval = max(max(a), max(b))
	mx = 0
	while mxval > 0:
		mxval = mxval >> 1
		mx += 1
	ans = 0
	cap = pow(2, mx - 1)
	for j in range(mx - 1, -1, -1):
		fg = 1
		bita = [(a[i] >> j) % 2 for i in range(n)]
		bitb = [(b[i] >> j) % 2 for i in range(n)]
		for i in range(n):
			if bita[i] ^ bitb[i] == 0:
				fg = 0
				break
		if fg == 0:
			for i in range(n):
				if bita[i] == 1:
					a[i] -= cap
				if bitb[i] == 1:
					b[i] -= cap
		cap = cap // 2
		a = sorted(a)
		b = sorted(b)[::-1]
	c = [a[i] ^ b[i] for i in range(n)]
	ans = c[0]
	for i in range(n):
		ans = ans & c[i]
	print(ans)