#include "secret.h"
int n, a[10005];
int pf[4005][1005], sf[4005][1005];
void build(int idx, int l, int r){
if(l == r){
pf[idx][l] = sf[idx][l] = a[l];
return;
}
int mid = (l + r) / 2;
sf[idx*2][mid] = a[mid];
for(int i=mid-1;i>=l;i--) sf[idx*2][i] = Secret(a[i], sf[idx*2][i+1]);
pf[idx*2+1][mid+1] = a[mid+1];
for(int i=mid+2;i<=r;i++) pf[idx*2+1][i] = Secret(pf[idx*2+1][i-1], a[i]);
build(idx*2, l, mid);
build(idx*2+1, mid+1, r);
// if(l == 0 && r == n-1) return;
// for(int i=l;i<=mid;i++) pf[idx][i] = pf[idx*2][i];
// for(int i=mid+1;i<=r;i++) pf[idx][i] = Secret(pf[idx][i-1], a[i]);
// for(int i=r;i>=mid+1;i--) sf[idx][i] = sf[idx*2+1][i];
// for(int i=mid;i>=l;i--) sf[idx][i] = Secret(a[i], sf[idx][i+1]);
}
int getRange(int idx, int l, int r, int u, int v){
int mid = (l + r) / 2;
if(v <= mid) return getRange(idx*2, l, mid, u, v);
if(mid < u) return getRange(idx*2+1, mid+1, r, u, v);
return Secret(sf[idx*2][u], pf[idx*2+1][v]);
}
void Init(int N, int A[]) {
n = N;
for(int i=0;i<N;i++) a[i] = A[i];
build(1, 0, N-1);
}
int Query(int L, int R) {
if(L == R) return a[L];
return getRange(1, 0, n-1, L, R);
}
