#include "secret.h"
const int maxn=1e3+5;
int dat[12][maxn],msk[maxn];
int arr[maxn];
void rec(int l,int r,int lev){
if(l==r){
return;
}
int mid=(l+r)/2;
dat[lev][mid]=arr[mid];
for(int i=mid-1;i>=l;i--) dat[lev][i]=Secret(arr[i],dat[lev][i+1]);
dat[lev][mid+1]=arr[mid+1];
for(int i=mid+2;i<=r;i++) dat[lev][i]=Secret(dat[lev][i-1],arr[i]);
for(int i=mid+1;i<=r;i++) msk[i]^=(1<<lev);
rec(l,mid,lev+1);
rec(mid+1,r,lev+1);
}
void Init(int N, int A[]) {
for(int i=0;i<N;i++) arr[i]=A[i];
rec(0,N-1,0);
}
int Query(int l,int r) {
if(l==r){
return arr[l];
}
int bits=__builtin_ctz(msk[l]^msk[r]);
return Secret(dat[bits][l],dat[bits][r]);
}
