#include "secret.h"
const int NMAX = 1000;
const int LOGMAX = 9;
int a[NMAX + 1], n;
int st[LOGMAX + 1][NMAX + 1];
int mask[NMAX + 1];
void precalc(int left, int right, int k) {
if(left == right) {
return;
}
int mid = (left + right) / 2;
st[k][mid] = a[mid];
for(int i = mid - 1; i >= left; i--) {
st[k][i] = Secret(a[i], st[k][i + 1]);
}
st[k][mid + 1] = a[mid + 1];
for(int i = mid + 2; i <= right; i++) {
st[k][i] = Secret(st[k][i - 1], a[i]);
}
for(int i = mid + 1; i <= right; i++) {
mask[i] |= (1 << k);
}
precalc(left, mid, k + 1);
precalc(mid + 1, right, k + 1);
}
void Init(int N, int A[]) {
for(int i = 1; i <= N; i++) {
a[i] = A[i - 1];
}
n = N;
precalc(1, n, 0);
}
int Query(int L, int R) {
L++; R++;
if(L == R) {
return a[L];
}
int k = __builtin_ctz(mask[L] ^ mask[R]);
return Secret(st[k][L], st[k][R]);
}
