#include "secret.h"
int n, a[1005], dt[10][1005];
void solve (int S, int E, int X) {
if(S == E) return;
int M = (S+E)/2;
dt[X][M] = a[M];
for(int i=M-1;i>=S;i--) {
dt[X][i] = Secret(a[i], dt[X][i+1]);
}
dt[X][M+1] = a[M+1];
for(int i=M+2;i<=E;i++) {
dt[X][i] = Secret(dt[X][i-1], a[i]);
}
solve(S, M, X+1);
solve(M+1, E, X+1);
}
int get (int S, int E, int SS, int SE, int X) {
int M = (SS+SE)/2;
if(E <= M) return get(S, E, SS, M, X+1);
if(S > M) return get(S, E, M+1, SE, X+1);
return Secret(dt[X][S], dt[X][E]);
}
void Init(int N, int A[]) {
n = N;
for(int i=0;i<n;i++) a[i] = A[i];
solve(0, n-1, 0);
}
int Query(int L, int R) {
if(L == R) return a[L];
return get(L, R, 0, n-1, 0);
}
