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 org.omg.CORBA.MARSHAL;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.*;
import java.io.*;
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////                                                                                                               /////////
////////                                                                                                               /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMM          MMMM         OOOOOO             SSSSSSS      EEEEEEEEEEEEE  /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMMMM      MMMMMM      OOO      OOO        SSSS   SSS     EEEEEEEEEEEEE  /////////
////////   HHHH        HHHH  EEEEE           MMMM MMM  MMM MMMM    OOO          OOO    SSSS       SSS   EEEEE          /////////
////////   HHHH        HHHH  EEEEE           MMMM  MMMMMM  MMMM   OOO            OOO   SSSS             EEEEE          /////////
////////   HHHH        HHHH  EEEEE           MMMM          MMMM  OOO              OOO   SSSSSSS         EEEEE          /////////
////////   HHHHHHHHHHHHHHHH  EEEEEEEEEEE     MMMM          MMMM  OOO              OOO      SSSSSS       EEEEEEEEEEE    /////////
////////   HHHHHHHHHHHHHHHH  EEEEEEEEEEE     MMMM          MMMM  OOO              OOO         SSSSSSS   EEEEEEEEEEE    /////////
////////   HHHH        HHHH  EEEEE           MMMM          MMMM   OOO            OOO              SSSS  EEEEE          /////////
////////   HHHH        HHHH  EEEEE           MMMM          MMMM    OOO          OOO     SSS       SSSS  EEEEE          /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMM          MMMM      OOO      OOO        SSS    SSSS    EEEEEEEEEEEEE  /////////
////////   HHHH        HHHH  EEEEEEEEEEEEE   MMMM          MMMM         OOOOOO             SSSSSSS      EEEEEEEEEEEEE  /////////
////////                                                                                                               /////////
////////                                                                                                               /////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

public class Contest1 {
    static int[][]memo;
    static int n;
    static HashSet<Integer>hs1,hs2,hs3;
    static int dp(int player,int val){
        if (val>n)return 0;
        if (memo[player][val]!=-1)return memo[player][val];
        int ans= (int) 1e8;
        if (player==0){
            ans=Math.min(dp(1,val),dp(0,val+1)+(hs1.contains(val)?0:1));
        }
        else if (player==1){
            ans=Math.min(dp(2,val),dp(1,val+1)+(hs2.contains(val)?0:1));
        }
        else {
            ans=dp(2,val+1)+(hs3.contains(val)?0:1);
        }
        return memo[player][val]=ans;
    }
    static class Obj implements Comparable<Obj>{
        int i ;
        int[]vals;
        Obj(int a,int[]b){
            i=a;
            vals=b;
        }

        public int compareTo(Obj obj) {
            for (int i =0;i<vals.length;i++){
                if (vals[i]!=obj.vals[i])
                    return vals[i]-obj.vals[i];
            }
            return 0;
        }
    }
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = sc.nextInt();
        int[]a=new int[n];
        for (int i =0;i<n;i++){
            a[i]=sc.nextInt();
        }
        TreeSet<Obj>meet=new TreeSet<>();
        Obj[]objs=new Obj[1<<15];
        for (int i =0;i<(1<<15);i++){
            int[]first=new int[n];
            int[]second=new int[n];
            for (int j=0;j<n;j++){
                first[j]=Integer.bitCount(i^(a[j]%(1<<15)));
                second[j]=Integer.bitCount(i^(a[j]>>15));
            }
            objs[i]=new Obj(i,first);
            meet.add(new Obj(i,second));
        }
        for (int i =0;i<objs.length;i++){
            for (int j =0;j<31;j++){
                int []c=new int[n];
                for (int k =0;k<n;k++){
                    c[k]=j-objs[i].vals[k];
                }
                if (meet.contains(new Obj(i,c))){
                    Obj z = meet.ceiling(new Obj(i,c));
                    pw.println(i+(z.i<<15));
                    pw.flush();
                    return;
                }

            }
        }
        pw.println(-1);
        pw.flush();
    }
    static long gcd(long a, long b) {
        if (a == 0) return b;
        return gcd(b % a, a);
    }
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if (x.charAt(0) == '-') {
                neg = true;
                start++;
            }
            for (int i = start; i < x.length(); i++)
                if (x.charAt(i) == '.') {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                } else {
                    sb.append(x.charAt(i));
                    if (dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg ? -1 : 1);
        }

        public boolean ready() throws IOException {
            return br.ready();


        }
    }

}