#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
using ll = long long;
const int mxN = 1e3+10;
int dat[12][mxN], mask[mxN];
vector<int> x;
int mx = 1000000000;
void divi(int l, int r, int lvl) {
if(l == r) return ;
int m = (l+r)/2;
dat[lvl][m] = x[m];
for(int i = m-1; i >= l; i--) {
if(x[i] > mx || x[i] < 0 || dat[lvl][i+1] > mx || dat[lvl][i+1] < 0) {
while(1) {
}
}
dat[lvl][i] = Secret(x[i], dat[lvl][i+1]);
}
dat[lvl][m+1] = x[m+1];
for(int i = m+2; i <= r; i++) {
if(x[i] > mx || x[i] < 0 || dat[lvl][i-1] > mx || dat[lvl][i-1] < 0) {
while(1) {
}
}
dat[lvl][i] = Secret(x[i], dat[lvl][i-1]);
}
for(int i = m+1; i <= r; i++) mask[i] ^= (1 << lvl);
divi(l, m, lvl+1); divi(m+1, r, lvl+1);
}
void Init(int n, int a[]) {
for(int i = 0; i < n; i++) {
int it = a[i];
x.push_back(it);
}
divi(0, n-1, 0);
}
int Query(int l, int r) {
if(l == r) return x[l];
int bits = __builtin_ctz(mask[l] ^ mask[r]);
return Secret(dat[bits][l], dat[bits][r]);
}
