#include "secret.h"
const int MX = 1000;
int dat[10][MX];
int mask[MX];
int a[MX];
void divi(int l, int r, int lev) {
if (l == r) return;
int m = (l+r)/2;
dat[lev][m] = a[m];
for (int i=m-1;i>=l;i--) {
dat[lev][i] = Secret(a[i], dat[lev][i+1]);
}
dat[lev][m+1] = a[m+1];
for (int i=m+2;i<=r;i++) {
dat[lev][i] = Secret(dat[lev][i-1], a[i]);
}
for (int i=m+1;i<=r;i++) {
mask[i] ^= (1<<lev);
}
divi(l, m, lev+1);
divi(m+1, r, lev+1);
}
void Init(int N, int A[]) {
for (int i=0;i<N;i++) {
a[i] = A[i];
}
divi(0, N-1, 0);
}
int Query(int L, int R) {
if (L == R) return a[L];
int bits = __builtin_ctz(mask[L] ^ mask[R]);
return Secret(dat[bits][L], dat[bits][R]);
}
