Today, as a friendship gift, Bakry gave Badawy $n$ integers $a_1, a_2, \dots, a_n$ and challenged him to choose an integer $X$ such that the value $\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$ is minimum possible, where $\oplus$ denotes the bitwise XOR operation.

As always, Badawy is too lazy, so you decided to help him and find the minimum possible value of $\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$.


-----Input-----

The first line contains integer $n$ ($1\le n \le 10^5$).

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


-----Output-----

Print one integer — the minimum possible value of $\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$.


-----Examples-----
Input
3
1 2 3

Output
2

Input
2
1 5

Output
4



-----Note-----

In the first sample, we can choose $X = 3$.

In the second sample, we can choose $X = 5$.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
seq = sorted(list(map(int, input().split())))

#Left (inc), Right(exc), bit to check, value to add 
queue = [(0,n,30,0)]
best = 2 ** 30
while queue:
    l, r, b, v = queue.pop()
    if b >= 0:
        mask = 1 << b
        
        if not mask & seq[l] and mask & seq[r - 1]:
            for i in range(l, r):
                if mask & seq[i]:
                    queue.append((l,i,b - 1, v + mask))
                    queue.append((i,r,b - 1, v + mask))
                    break
        else:
            queue.append((l, r, b - 1, v))
    else:
        best = min(best, v)
        
print(best)


import sys
input = sys.stdin.readline

n=int(input())
A=tuple(map(int,input().split()))

ANS=0

def calc(A,ANS,keta):
    if keta==-1:
        return ANS
    
    Z=[]
    O=[]
    
    for a in A:
        if a & (1<<keta)!=0:
            Z.append(a)
        else:
            O.append(a)

    if Z==[] or O==[]:
        return calc(A,ANS,keta-1)

    else:
        return min(calc(Z,ANS+(1<<keta),keta-1),calc(O,ANS+(1<<keta),keta-1))

print(calc(A,0,30))
    
    
    


import sys

X = int(sys.stdin.readline())

a = set([int(i) for i in sys.stdin.readline().split()])

top = 1<<31
ans = 0

def best(s, cur):
    if len(s) == 0 or cur==0:
        return 0
    hasCur = set()
    hasNotCur = set()
    for i in s:
        if i&cur == 0:
            hasNotCur.add(i)
        else:
            hasCur.add(i)
    if len(hasNotCur)==0 or len(hasCur)==0:
        return best(s, cur>>1)
    else:
        return cur + min(best(hasNotCur, cur>>1), best(hasCur, cur>>1))

print(best(a, top))


from sys import stdin
input = stdin.readline
n = int(input())
l = list(map(int,input().split()))
cyk = [1] * 50
for i in range(1,50):
	cyk[i] = cyk[i-1] * 2
def wyn(lista):
	m = max(lista)
	if m == min(lista):
		return 0
	le = len(bin(m))
	duze = []
	male = []
	pyk = cyk[le-3]
	for i in lista:
		if i >= cyk[le-3]:
			duze.append(i - pyk)
		else:
			male.append(i)
	if len(male) == 0:
		k = [lista[i]-pyk for i in range(len(lista))]
		return wyn(k)
	else:
		return pyk + min(wyn(duze),wyn(male))
print(wyn(l))