#include "secret.h"
#define MAXN 1001
int dat[MAXN][12];
int mask[MAXN];
void divi(int l, int r, int lev, int A[]){ //zero indexed
if( l == r ){ dat[l][11] = A[l]; return; }
int m = (l+r)/2;
dat[m][lev] = A[m];
dat[m+1][lev] = A[m+1]; //makes a difference in this case
for( int i{m-1} ; i >= l ; --i ) dat[i][lev] = Secret(A[i], dat[i+1][lev]);
for( int i{m+2} ; i <= r ; ++i ) dat[i][lev] = Secret(dat[i-1][lev], A[i]);
for( int i{m+1} ; i <= r ; ++i ) mask[i] ^= (1<<lev);
divi(l, m, lev+1, A);
divi(m+1, r, lev+1, A);
}
void Init(int N, int A[]) {
divi(0, N-1, 0, A);
return;
}
int Query(int L, int R) {
if( L == R ) return dat[L][11];
int bts = __builtin_ctz(mask[L]^mask[R]);
int ans = Secret(dat[L][bts], dat[R][bts]);
return ans;
}
