Let's call two numbers similar if their binary representations contain the same number of digits equal to 1. For example:

  * 2 and 4 are similar (binary representations are 10 and 100); 
  * 1337 and 4213 are similar (binary representations are 10100111001 and 1000001110101); 
  * 3 and 2 are not similar (binary representations are 11 and 10); 
  * 42 and 13 are similar (binary representations are 101010 and 1101). 



You are given an array of n integers a_1, a_2, ..., a_n. You may choose a non-negative integer x, and then get another array of n integers b_1, b_2, ..., b_n, where b_i = a_i ⊕ x (⊕ denotes bitwise XOR).

Is it possible to obtain an array b where all numbers are similar to each other?

Input

The first line contains one integer n (2 ≤ n ≤ 100).

The second line contains n integers a_1, a_2, ..., a_n (0 ≤ a_i ≤ 2^{30} - 1).

Output

If it is impossible to choose x so that all elements in the resulting array are similar to each other, print one integer -1.

Otherwise, print any non-negative integer not exceeding 2^{30} - 1 that can be used as x so that all elements in the resulting array are similar.

Examples

Input


2
7 2


Output


1


Input


4
3 17 6 0


Output


5


Input


3
1 2 3


Output


-1


Input


3
43 12 12


Output


1073709057

Difficulty: VERY_HARD
Tags: String algorithms

Bit manipulation

Complete search
Skill types: Bit manipulation

Complete search

Starter code:

Solutions:
def main():
	import sys
	input = sys.stdin.readline
	N = int(input())
	A = list(map(int, input().split()))
	dic1 = {}
	dic2 = {}
	A1 = [0] * N
	for (i, a) in enumerate(A):
		A1[i] = a >> 15
	for i in range(2 ** 15):
		tmp = [0] * N
		for (j, a) in enumerate(A1):
			a ^= i
			tmp[j] = bin(a).count('1')
		t0 = tmp[0]
		for j in range(N):
			tmp[j] -= t0
		dic1[i] = tuple(tmp)
	A2 = [0] * N
	for (i, a) in enumerate(A):
		A2[i] = a % 2 ** 15
	for i in range(2 ** 15):
		tmp = [0] * N
		for (j, a) in enumerate(A2):
			a ^= i
			tmp[j] = -bin(a).count('1')
		t0 = tmp[0]
		for j in range(N):
			tmp[j] -= t0
		dic2[tuple(tmp)] = i
	for i in range(2 ** 15):
		if dic1[i] in dic2:
			print(i * 2 ** 15 + dic2[dic1[i]])
			exit()
	print(-1)
main()


import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
	n = ni()
	a = nl()
	mask = (1 << 15) - 1
	ab = [x & mask for x in a]
	at = [x >> 15 for x in a]
	d = dict()
	for bit in range(mask, -1, -1):
		b = [bin(bit ^ x).count('1') for x in ab]
		g = tuple([x - b[0] for x in b[1:]])
		d[g] = bit
	for bit in range(mask + 1):
		b = [bin(bit ^ x).count('1') for x in at]
		g = tuple([b[0] - x for x in b[1:]])
		if g in d:
			print(bit << 15 | d[g])
			return
	print(-1)
	return
solve()


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def popcnt_32(x):
	x = (x & 1431655765) + (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	return x + (x >> 16) & 63

def hash(a, mod1=10 ** 9 + 7, mod2=10 ** 9 + 9):
	base = 123456789
	res1 = 0
	res2 = 0
	for x in a:
		res1 = (res1 * base + x) % mod1
		res2 = (res2 * base + x) % mod2
	return (int(str(res1)), int(str(res2)))

def main():
	n = int(input())
	(mask, lower, upper) = (2 ** 15 - 1, [], [])
	for x in map(int, input().split()):
		lower.append(x & mask)
		upper.append(x >> 15)
	d = {}
	(delta1, delta2) = hash([1] * n)
	(mod1, mod2) = (10 ** 9 + 7, 10 ** 9 + 9)
	for bit in range(1 << 15):
		d[hash(map(lambda x: popcnt_32(x ^ bit), lower))] = bit
	for bit in range(1 << 15):
		pc = [popcnt_32(x ^ bit) for x in upper]
		(key1, key2) = hash((-p for p in pc))
		for base in range(30):
			if (key1, key2) in d:
				print((bit << 15) + d[key1, key2])
				exit()
			key1 = (key1 + delta1) % mod1
			key2 = (key2 + delta2) % mod2
	print(-1)
main()


def bitcount(x):
	return 0 if x == 0 else x % 2 + bitcount(x // 2)

def core():
	_ = int(input())
	A = [int(v) for v in input().split()]
	Hmask = 1073709056
	Lmask = 32767
	H = [a >> 15 for a in A]
	L = [a & Lmask for a in A]
	Hcnt = {}
	Lcnt = {}
	for x in range(2 ** 15):
		hkey = [bitcount(h ^ x) for h in H]
		shift = min(hkey)
		hkey = tuple((v - shift for v in hkey))
		Hcnt.setdefault(hkey, x)
		Hcnt[hkey] = min(Hcnt[hkey], x)
		lkey = tuple((bitcount(l ^ x) for l in L))
		Lcnt.setdefault(lkey, x)
		Lcnt[lkey] = min(Lcnt[lkey], x)
	for t in Lcnt:
		reverse_t = tuple((max(t) - v for v in t))
		shift = min(reverse_t)
		shifted_rt = tuple((shift + v for v in reverse_t))
		if shifted_rt in Hcnt:
			ans = Hcnt[shifted_rt] << 15 | Lcnt[t]
			return ans
	return -1
print(core())


H = 15
n = int(input())
a = list(map(int, input().split()))

def pc(v):
	v = v - (v >> 1 & 1431655765)
	v = (v & 858993459) + (v >> 2 & 858993459)
	return ((v + (v >> 4) & 252645135) * 16843009 & 4294967295) >> 24
mask = (1 << H) - 1
rec = {}
for x in range(1 << H):
	r = [pc(ai & mask ^ x) for ai in a]
	d = tuple((r[-1] - ri for ri in r[:-1]))
	rec.setdefault(d, x)
ans = None
mask = (1 << H) - 1 << H
for x in range(1 << H):
	x <<= H
	r = [pc(ai & mask ^ x) for ai in a]
	y = rec.get(tuple((ri - r[-1] for ri in r[:-1])), None)
	if y is not None:
		ans = x | y
		break
print(-1 if ans is None else ans)


H = 15
MASK = (1 << H) - 1
n = int(input())
a = list(map(int, input().split()))
rec = {}
for x in range(1 << H):
	r = [bin(ai & MASK ^ x).count('1') for ai in a]
	d = tuple((r[-1] - ri for ri in r[:-1]))
	rec.setdefault(d, x)
ans = None
for x in range(1 << H):
	r = [bin(ai >> H ^ x).count('1') for ai in a]
	y = rec.get(tuple((ri - r[-1] for ri in r[:-1])), None)
	if y is not None:
		ans = x << H | y
		break
print(-1 if ans is None else ans)


n = int(input())
arr = list(map(int, input().split()))
msbs_achieved_by = {tuple((bin(num >> 15 ^ x).count('1') for num in arr)): x for x in range(1 << 15)}

def main():
	for x in range(1 << 15):
		counts = [bin(x ^ num & (1 << 15) - 1).count('1') for num in arr]
		for common_count in range(max(counts), 31):
			other_counts = tuple((common_count - s for s in counts))
			found = msbs_achieved_by.get(other_counts)
			if found:
				result = found << 15 | x
				print(result)
				arr2 = [result ^ num for num in arr]
				return
	print(-1)
main()


n = int(input())
d = [int(i) for i in input().split()]
l1 = [[1] * n for i in range(15)]
l2 = [[1] * n for i in range(15)]
vec_const1 = [0] * n
vec_const2 = [0] * n
for j in range(n):
	dd = d[j]
	for i in range(30):
		if dd & 1 << i:
			if i < 15:
				vec_const1[j] += 1
				l1[i][j] = -1
			else:
				vec_const2[j] += 1
				l2[i - 15][j] = -1
ub = 1 << 15
dic = {}
for msk in range(ub):
	mask = msk
	vec = vec_const1[:]
	for i in range(15):
		if mask & 1:
			for j in range(n):
				vec[j] += l1[i][j]
		mask >>= 1
	dic[tuple([vec[i + 1] - vec[i] for i in range(n - 1)])] = msk
for msk in range(ub):
	vec = vec_const2[:]
	mask = msk
	for i in range(15):
		if mask & 1:
			for j in range(n):
				vec[j] += l2[i][j]
		mask >>= 1
	dif = tuple([vec[i] - vec[i + 1] for i in range(n - 1)])
	if dif in dic:
		print((msk << 15) + dic[dif])
		exit()
print(-1)