#include "secret.h"
#include <algorithm>
using namespace std;
namespace {
const int MAXN = 1000;
int pref[4*MAXN + 10][MAXN + 10], suff[4*MAXN + 10][MAXN + 10];
int *A, N;
void build(int cn, int b, int e) {
if(b == e) return;
int m = (b + e) / 2;
int L = cn << 1, R = L | 1;
suff[L][m] = A[m];
for(int i = m-1; i >= b; i--) {
suff[L][i] = Secret(A[i], suff[L][i+1]);
}
pref[R][m+1] = A[m+1];
for(int i = m+2; i <= e; i++) {
pref[R][i] = Secret(pref[R][i-1], A[i]);
}
build(L, b, m); build(R, m+1, e);
}
};
void Init(int N_, int *A_) {
N = N_;
A = A_;
build(1, 0, N-1);
pref[1][N-1] = Secret(suff[2][0], pref[3][N-1]);
}
int Query(int l, int r) {
int cn = 1, b = 0, e = N-1;
while(true) {
if(l == b && r == e) {
if(cn & 1) return pref[cn][r];
else return suff[cn][l];
}
int m = (b + e) / 2;
if(l <= m && m <= r) {
if(r == m) return suff[cn<<1][l];
else return Secret(suff[cn<<1][l], pref[cn<<1|1][r]);
}
if(r <= m) {
cn = cn << 1;
e = m;
} else {
cn = cn<<1 | 1;
b = m+1;
}
}
}
