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.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.List;
 import java.util.*;
 public class realfast implements Runnable 
  {
    private static final int INF = (int) 1e9;
    long in= 998244353;
    long fac[]= new long[3000];
    public  void solve() throws IOException 
    {
      

      int n = readInt();

      int arr[]=new int[n];

      for(int i =0;i<n;i++)
        arr[i]= readInt();


      int b[]=new int[n];
      int c[]=new int[n];
       int yo = 1<<15;
       yo--;
      for(int i =0;i<n;i++)
      {
        b[i]= yo&arr[i];
        c[i]= arr[i]-b[i];
      }


      HashMap<Long,Integer>map = new HashMap<>();

      Random r =new Random();
      long hash[]=new long[n];

      for(int i=0;i<n;i++)
        hash[i]= r.nextLong();


      for(int i =0;i<=(yo);i++)
      {
        long c1 =0;
        for(int j =0;j<n;j++)
        {
             int l = i^b[j];
             int count =0;
             while(l!=0)
             {
               int kl=l%2;
               if(kl==1)
                count++;
               l=l/2;
             }
             c1= c1+ hash[j]*count;
        }
        map.put(c1,i);

      }

        boolean check = false;
       
      for(int i =0;i<=yo;i++)
      {
        int lo = i*(yo+1);
        int max =0;
        int count[]=new int[n];
        for(int j =0;j<n;j++)
        {
            int l = lo^c[j];
            while(l!=0)
            {
              if(l%2==1)
                count[j]++;
              l=l/2;
            }
            max=Math.max(max,count[j]);
        }

        long c1=0;
        for(int k=max;k<=15;k++)
        {
          c1 =0;
         for(int j =0;j<n;j++)
         {
            c1 =c1 + (k-count[j])*hash[j];
         }
         if(map.containsKey(c1))
         {
            int kl=map.get(c1);
             kl =kl+lo;
             System.out.println(kl);
             check=true;
             break;
         }
         if(check)
            break;
        }
        if(check)
            break;
      }

      if(!check)
        System.out.println(-1);



           
      

    }
   
    
    public int value (int seg[], int left , int right ,int index, int l, int r)
    {
            
            if(left>right)
            {
              return -100000000;
            }
            if(right<l||left>r)
                return -100000000;
            if(left>=l&&right<=r)
                return seg[index];
            int mid = left+(right-left)/2;
            int val = value(seg,left,mid,2*index+1,l,r);
            int val2 = value(seg,mid+1,right,2*index+2,l,r);
            return Math.max(val,val2);

    }
   
    public int gcd(int a , int b )
    {
      if(a<b)
      {
        int t =a;
        a=b;
        b=t;
      }
      if(a%b==0)
        return b ;
      return gcd(b,a%b);
    }
    public long pow(long n , long p,long m)
    {
         if(p==0)
            return 1;
        long val = pow(n,p/2,m);;
        val= (val*val)%m;
        if(p%2==0)
            return val;
        else
            return (val*n)%m;
    }
    
    
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public static void main(String[] args) {
        new Thread(null, new realfast(), "", 128 * (1L << 20)).start();
    }
 
    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    private BufferedReader reader;
    private StringTokenizer tokenizer;
    private PrintWriter out;
 
    @Override
    public void run() {
        try {
            if (ONLINE_JUDGE || !new File("input.txt").exists()) {
                reader = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                reader = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            solve();
        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            try {
                reader.close();
            } catch (IOException e) {
                // nothing
            }
            out.close();
        }
    }
 
    private String readString() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
 
    @SuppressWarnings("unused")
    private int readInt() throws IOException {
        return Integer.parseInt(readString());
    }
 
    @SuppressWarnings("unused")
    private long readLong() throws IOException {
        return Long.parseLong(readString());
    }
 
    @SuppressWarnings("unused")
    private double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }
}
class edge implements Comparable<edge>{
    int val ;
    int color;
    
    edge(int u, int v)
    {
       this.val=u;
       this.color=v;
    }
    public int compareTo(edge e)
    {
        return this.val-e.val;
    }
}