Problem: 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

Solution (in JAVA):

Solution:
// Coached by rainboy
import java.io.*;
import java.util.*;

public class CF1257F extends PrintWriter {
	CF1257F() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1257F o = new CF1257F(); o.main(); o.flush();
	}

	static final int MD = 0x7fffffff, N = 100;
	static final Random rand = new Random();
	static final int X = rand.nextInt(MD - N) + N;
	static final int Y = rand.nextInt(MD - N) + N;
	static int count(int a) {
		return a == 0 ? 0 : count(a & a - 1) + 1;
	}
	static int[] kk = new int[N];
	static long hash(int n, int x) {
		long h = 0;
		for (int i = 0; i < n; i++)
			h = (h * x + kk[i]) % MD;
		if (h < 0)
			h += MD;
		return h;
	}
	static class V {
		long h;
		int c, lr;
		V(int[] aa, int n, int c, int lr) {
			for (int i = 0; i < n; i++)
				kk[i] = count(aa[i] ^ c);
			for (int i = 0; i < n - 1; i++)
				kk[i] = lr == 0 ? kk[i + 1] - kk[i] : kk[i] - kk[i + 1];
			h = hash(n - 1, X) * MD + hash(n - 1, Y);
			this.c = c; this.lr = lr;
		}
	}
	void main() {
		int n = sc.nextInt();
		int[] aa = new int[n];
		int[] bb = new int[n];
		for (int i = 0; i < n; i++) {
			int ab = sc.nextInt();
			aa[i] = ab >> 15;
			bb[i] = ab & (1 << 15) - 1;
		}
		V[] vv = new V[1 << 16];
		for (int c = 0; c < 1 << 15; c++) {
			vv[c << 1] = new V(aa, n, c, 0);
			vv[c << 1 | 1] = new V(bb, n, c, 1);
		}
		Arrays.sort(vv, (u, v) -> u.h != v.h ? (u.h < v.h ? -1 : 1) : u.lr - v.lr);
		long ans = -1;
		for (int i = 1; i < 1 << 16; i++)
			if (vv[i - 1].h == vv[i].h && vv[i - 1].lr != vv[i].lr) {
				ans = vv[i - 1].c << 15 | vv[i].c;
				break;
			}
		println(ans);
	}
}