#include "secret.h"
#define N 1000
#define M 10000
int bb[M], *ptr, *cc[N], n;
void solve(int *aa, int l, int r) {
int m, i;
if (l > r)
return;
m = (l + r) / 2;
cc[m] = ptr, ptr += r - l + 1;
cc[m][m - l] = aa[m];
for (i = m - 1; i >= l; i--)
cc[m][i - l] = Secret(aa[i], cc[m][i + 1 - l]);
if (l < r) {
cc[m][m + 1 - l] = aa[m + 1];
for (i = m + 2; i <= r; i++)
cc[m][i - l] = Secret(cc[m][i - 1 - l], aa[i]);
}
solve(aa, l, m - 1), solve(aa, m + 2, r);
}
void Init(int n_, int *aa) {
n = n_, ptr = bb, solve(aa, 0, n - 1);
}
int query(int l, int r, int ql, int qr) {
int m = (l + r) / 2;
if (qr == m)
return cc[m][ql - l];
if (ql == m + 1)
return cc[m][qr - l];
if (ql <= m && m + 1 <= qr)
return Secret(cc[m][ql - l], cc[m][qr - l]);
return qr < m ? query(l, m - 1, ql, qr) : query(m + 2, r, ql, qr);
}
int Query(int l, int r) {
return query(0, n - 1, l, r);
}
