Given an array of n non-negative integers: A₁, A₂, …, A_N. Your mission is finding a pair of integers A_u,A_v (1 ≤ u < v ≤ N) such that (A_u and A_v) is as large as possible.
And is a bit-wise operation which is corresponding to & in C++ and Java.

Input

The first line of the input contains a single integer N. The ith line in the next N lines contains the A_i.

Output

Contains a single integer which is the largest value of A_u and A_v where 1 ≤ u < v ≤ N.

Constraints

50 points:

• 2 ≤ N ≤ 5000
• 0 ≤ A_i ≤ 10⁹

50 points:

• 2 ≤ N ≤ 3 × 10⁵
• 0 ≤ A_i ≤ 10⁹

Example

Input:
4
2
4
8
10

Output:
8

Explanation

• 2 and 4 = 0
• 2 and 8 = 0
• 2 and 10 = 2
• 4 and 8 = 0
• 4 and 10 = 0
• 8 and 10 = 8

When we are ANDing two numbers, we would like to have a 1 at the most significant bit(MSB). So, first we'll try to get a 1 at MSB. Now, suppose we denote A[i]=b_i_n,b_i_n-1...b_i₀, where b_i's are the bits that could be 1 or 0.

Let's say S be the set of A[i] whose b_i_n is 1 and S' be the set of A[i] whose b_i_n is 0. If size of S ≥ 2 we are sure that our answer will be maximum if we chose a pair of numbers from S, because n'th bit of their AND will be 1 for sure. So, we know our answer lies in S.

However, if size of S is less than 2, we can never have n'th bit 1 in our answer. So, we'll have to continue with n'th bit as 0. Note that our answer will now be in S'.

Now, we know our answer is in S or S' and we also know n'th bit of our answer. So, our new subproblem is to find (n-1)'th bit of our answer using numbers in S or S'. We can write a recursive code for this. What will be the complexity? For each of the n bits, we'll traverse whole array to sort according to their bits. So O(n*N). We will be keeping n=30, because A[i] ≤ 10⁹.

n=input()
arr=[]
flag[n]={}
for i=0 to n-1:
    arr[i]=input()
print foo(30)

def foo(level):  //this function will find the level'th bit
                //and accordingly return answer
    if level==-1:  // we already have solved for all bits. return 0 from here
        return 0
    Scount=0  // stores the size of set S
    ans=0 // the answer in decimal form
    for i=0 to n-1:
        if flag[i]==0:  // flag[i]=0 means arr[i] is available for us to use
            if (arr[i]&(1<<level)): // level'th bit of arr[i] is 1
                Scount++
    if Scount>=2: // our answer's level'th bit will be 1
        ans += (1<<level)
        // but we also have to set the flag of unavailable numbers
        for i=0 to n-1:
            if (arr[i]&(1<<level))==0:  // level'th bit is 0, set the flag
                flag[i]=1
    return ans+foo(level-1);  // return the current answer + answer for the next bit

code goes here

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define mp make_pair
list<int> sup[100010];
long long int val[100010];
bool visited[100010];
long long int arr[100010];
int top=0;
long long int sttime[100010];
long long int endtime[100010];
long long int vis=0;
long long int  t[1000100];

void build(int node, int a, int b)
{
 if(a>b) return;
 if (a==b)
 {
  t[node]=arr[a];
  return;
 }
 
 build(node*2, a, (a+b)/2);
 build(node*2+1,(a+b)/2+1,b);
 
 t[node]=t[node*2]+t[node*2+1];
}

long long int  query(int node, int a, int b, int i, int j)
{
 if(a>b||a>j||b<i) return 0;
 
 if (a>=i && b<=j) return t[node];
 
 int q1=query(node*2, a, (a+b)/2, i, j);
 int q2=query(node*2+1, (a+b)/2+1, b, i, j);
 
 return q1+q2;
}

void update(int node, int a, int b, int i, int j, long long int inc)
{
 if(a>b) return;
 
 if(a>b||a>j||b<i) return;
 
 if (a>=i && b<=j)
 {
  t[node]=inc;
  
  return;
 }
 
 update(node*2, a, (a+b)/2, i, j, inc);
 update(node*2+1, (a+b)/2+1, b,i, j, inc);
 t[node] = t[node*2] + t[node*2+1];
}
void dfs(int st)
{
 //cout<<"called "<<st<<" tm "<<vis<<endl;
     list<int> ::iterator it;
     arr[vis]=val[st];  
     sttime[st]=vis;
     visited[st]=1;
     for( it=sup[st].begin();it!=sup[st].end();it++)
     {
      if(visited[*it]==0)
      {
            vis++;
     visited[*it]=1;  
     dfs(*it);
     
    }
     }
   //  cout<<"enfing "<<st<<" with "<<vis<<endl;
     endtime[st]=vis;
}
int main()
{
 int n;
 cin>>n;
 int q;
 cin>>q;
 for(int i=0;i<n;i++)
 {
  scanf("%d",&val[i]);
 }
 
 for(int i=0;i<n-1;i++)
 {
  int a,b;
  scanf("%d %d",&a,&b);
  a=a-1;
  b=b-1;
  //cout<<" a and b "<<a<<" "<<b<<endl;
  sup[a].push_back(b);
  sup[b].push_back(a);
 }
// cout<<sup[0].size()<<endl;
// cout<<"size "<<endl;
  visited[0]=1;
 dfs(0);

 //cout<<"done "<<endl;
/* for(int i=0;i<n;i++)
 {
  cout<<arr[i]<<" ";
 }
 cout<<endl;
 for(int i=0;i<n;i++)
 {
  cout<<sttime[i]<<" ";
 }
 cout<<endl;
 for(int i=0;i<n;i++)
 {
  cout<<endtime[i]<<" ";
 }
 cout<<endl;*/
 
 build(1,0,n-1);
 //cout<<endl;
 char str[5];
 while(q--)
 {
  int node;long long int  val;
  scanf("%s",str);
  if(str[0]=='Q')
  {
   cin>>val;
   val--;
   int qs,qe;
   qs=sttime[val];
   qe=endtime[val];
  // cout<<"query "<<qs<<" "<<qe<<endl;
   long long int ans=query(1,0,n-1,qs,qe);
    cout<<ans<<endl;
  }
  else
  {
      cin>>node>>val;
      node--;
      
      int upl=sttime[node];
      int upu=sttime[node];
      update(1,0,n-1,upl,upu,val);
  }
 }
 return 0;
}