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:
import java.io.*;
import java.util.*;
 
 
 
public class Main {
	
	static InputReader in = new InputReader(System.in);
	static PrintWriter out = new PrintWriter(System.out);
	
//	static int oo = (int)1e9;
	static long oo = (long)1e15;
	static int mod = 1_000_000_007;
	
	static int[] di = {1, 0, 0, -1};
	static int[] dj = {0, -1, 1, 0};
	
	static int M = 100005;
	static double EPS = 1e-5;
	
	public static void main(String[] args) throws IOException {

		int n = in.nextInt();
		int[] a = in.nextIntArray(n);
		
		
		X[] left = new X[1<<15];
		X[] right = new X[1<<15];
		
		for(int i = 0; i < (1<<15); ++i) {
			int x = i<<15;
			ArrayList<Integer> arr = new ArrayList<Integer>();
			int fc = -1;
			for(int j = 0; j < n; ++j) {
				int mask = ((1<<15) - 1) << 15;
				int r = (a[j] & mask) ^ x;
				int bc = Integer.bitCount(r);
				if(fc == -1)
					fc = bc;
				else
					arr.add(bc - fc);
			}
			left[i] = new X(x, arr); 
		}
		
		for(int i = 0; i < (1<<15); ++i) {
			int x = i;
			ArrayList<Integer> arr = new ArrayList<Integer>();
			int fc = -1;
			for(int j = 0; j < n; ++j) {
				int mask = (1<<15) - 1;
				int r = (a[j] & mask) ^ i;
				int bc = Integer.bitCount(r);
				if(fc == -1)
					fc = bc;
				else
					arr.add(bc - fc);
			}
			right[i] = new X(x, arr);
		}

		Arrays.parallelSort(right);
		
		
		for(X xx : left) {
			ArrayList<Integer> need = new ArrayList<Integer>();
			for(int bc : xx.res) {
				need.add(-bc);
			}
			int i = Arrays.binarySearch(right, new X(-1, need));
			if(i >= 0) {
				X yy = right[i];
				int ans = xx.x + yy.x;
				System.out.println(ans);
				return;
			}
		}
		System.out.println(-1);
		
		out.close();
	}
	
	static class X implements Comparable<X> {
		int x;
		ArrayList<Integer> res;
		public X(int x, ArrayList<Integer> res) {
			super();
			this.x = x;
			this.res = res;
		}
		@Override
		public int compareTo(X o) {
			for(int i = 0; i < res.size(); ++i) {
				if(i >= o.res.size())
					return 1;
				int x = res.get(i), y = o.res.get(i);
				if(x != y)
					return Integer.compare(x, y);
			}
			return o.res.size() > res.size() ? -1 : 0;
		}
	}
	
	
	
	static Pair dfs(ArrayList<Integer>[] adj, boolean[] visit, int u) {
		if(visit[u])
			return new Pair(Integer.MAX_VALUE, Integer.MIN_VALUE);
		visit[u] = true;
		int min = u, max = u;
		for(int v : adj[u]) {
			if(!visit[v]) {
				Pair p = dfs(adj, visit, v);
				min = Math.min(min, p.first);
				max = Math.max(max, p.second);
			}
		}
		return new Pair(min, max);
	}
	
	
	static boolean inside(int i, int j, int n, int m) {
		return i >= 0 && i < n && j >= 0 && j < m;
	}
	
	
	static long pow(long a, long n, long mod) {
		if(n == 0)
			return 1;
		if(n % 2 == 1)
			return a * pow(a, n-1, mod) % mod;
		long x = pow(a, n / 2, mod);
		return x * x % mod;
	}
	
	
	static class SegmentTree {
		int n;
		int[] a;
		int[] seg;
		int DEFAULT_VALUE = 0;
		
		public SegmentTree(int[] a, int n) {
			super();
			this.a = a;
			this.n = n;
			seg = new int[n * 4 + 1];
			build(1, 0, n-1);
		}
		
		private int build(int node, int i, int j) {
			if(i == j) {
				return seg[node] = a[i];
			}
			int first = build(node * 2, i, (i+j) / 2);
			int second = build(node * 2 + 1, (i+j) / 2 + 1, j);
			return seg[node] = combine(first, second);
		}
		
		int update(int k, char value) {
			return update(1, 0, n-1, k, value);
		}
		
		private int update(int node, int i, int j, int k, char value) {
			if(k < i || k > j)
				return seg[node];
			if(i == j && j == k) {
				a[k] = value;
				return seg[node] = value;
			}
			int m = (i + j) / 2;
			int first = update(node * 2, i, m, k, value);
			int second = update(node * 2 + 1, m + 1, j, k, value);
			return seg[node] = combine(first, second);
		}
		
		int query(int l, int r) {
			return query(1, 0, n-1, l, r);
		}
		
		private int query(int node, int i, int j, int l, int r) {
			if(l <= i && j <= r)
				return seg[node];
			if(j < l || i > r)
				return DEFAULT_VALUE;
			int m = (i + j) / 2;
			int first = query(node * 2, i, m, l, r);
			int second = query(node * 2 + 1, m+1, j, l, r);
			return combine(first, second);
		}
 
		private int combine(int a, int b) {
			return Math.max(a, b);
		}
	}
	
	static class DisjointSet {
		int n;
		int[] g;
		int[] h;
		public DisjointSet(int n) {
			super();
			this.n = n;
			g = new int[n];
			h = new int[n];
			for(int i = 0; i < n; ++i) {
				g[i] = i;
				h[i] = 1;
			}
		}
		int find(int x) {
			if(g[x] == x)
				return x;
			return g[x] = find(g[x]);
		}
		void union(int x, int y) {
			x = find(x); y = find(y);
			if(x == y)
				return;
			if(h[x] >= h[y]) {
				g[y] = x;
				if(h[x] == h[y])
					h[x]++;
			}
			else {
				g[x] = y;
			}
		}
	}
	
	
	static int[] getPi(char[] a) {
		int m = a.length;
		int j = 0;
		int[] pi = new int[m];
		for(int i = 1; i < m; ++i) {
			while(j > 0 && a[i] != a[j])
				j = pi[j-1];
			if(a[i] == a[j]) {
				pi[i] = j + 1;
				j++;
			}
		}
		return pi;
	}
	
	static long lcm(long a, long b) {
		return a * b / gcd(a, b);
	}
	
	static boolean nextPermutation(int[] a) {
		for(int i = a.length - 2; i >= 0; --i) {
			if(a[i] < a[i+1]) {
				for(int j = a.length - 1; ; --j) {
					if(a[i] < a[j]) {
						int t = a[i];
						a[i] = a[j];
						a[j] = t;
						for(i++, j = a.length - 1; i < j; ++i, --j) {
							t = a[i];
							a[i] = a[j];
							a[j] = t;
						}
						return true;
					}
				}
			}
		}
		return false;
	}
	
	static void shuffle(Object[] a) {
		Random r = new Random();
		for(int i = a.length - 1; i > 0; --i) {
			int si = r.nextInt(i);
			Object t = a[si];
			a[si] = a[i];
			a[i] = t;
		}
	}
	
	static void shuffle(int[] a) {
		Random r = new Random();
		for(int i = a.length - 1; i > 0; --i) {
			int si = r.nextInt(i);
			int t = a[si];
			a[si] = a[i];
			a[i] = t;
		}
	}
	
	static void shuffle(long[] a) {
		Random r = new Random();
		for(int i = a.length - 1; i > 0; --i) {
			int si = r.nextInt(i);
			long t = a[si];
			a[si] = a[i];
			a[i] = t;
		}
	}
	
	static int lower_bound(int[] a, int n, int k) {
		int s = 0;
		int e = n;
		int m;
		while (e - s > 0) {
			m = (s + e) / 2;
			if (a[m] < k)
				s = m + 1;
			else
				e = m;
		}
		return e;
	}
	static int lower_bound(long[] a, int n, long k) {
		int s = 0;
		int e = n;
		int m;
		while (e - s > 0) {
			m = (s + e) / 2;
			if (a[m] < k)
				s = m + 1;
			else
				e = m;
		}
		return e;
	}
	
	static int gcd(int a, int b) {
		return b == 0 ? a : gcd(b, a % b);
	}
	static long gcd(long a, long b) {
		return b == 0 ? a : gcd(b, a % b);
	}
	
	static class Pair implements Comparable<Pair> {
		int first, second;
 
		public Pair(int first, int second) {
			super();
			this.first = first;
			this.second = second;
		}
 
		@Override
		public int compareTo(Pair o) {
			return this.first != o.first ? this.first - o.first : this.second - o.second;
		}
		
//		@Override
//		public int compareTo(Pair o) {
//			return this.first != o.first ? o.first - this.first : o.second - this.second;
//		}
 
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + first;
			result = prime * result + second;
			return result;
		}
 
		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Pair other = (Pair) obj;
			if (first != other.first)
				return false;
			if (second != other.second)
				return false;
			return true;
		}
	}
}
 
 
 
class InputReader {
 
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;
 
	public InputReader(InputStream st) {
		this.stream = st;
	}
 
	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}
 
	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
 
	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
 
	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}
 
	public String readString() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}
 
	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}
 
	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}
 
	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
 
}