#include "secret.h"
#include <vector>
using namespace std;
const int maxD = 10;
vector<int> toright [maxD], toleft [maxD];
int *CA;
void Init(int N, int A[]) {
CA = A;
for (int rz = 0; rz < maxD; ++rz) {
toright[rz].resize(N);
toleft[rz].resize(N);
}
for (int k = 0; k < maxD; k++){
for (int cen = 1 << k; cen < N; cen += 1 << (k+1)) {
toright[k][cen - 1] = A[cen - 1];
for (int lpop = cen - 2; lpop >= cen - (1 << k); --lpop) {
toright[k][lpop] = Secret(A[lpop], toright[k][lpop + 1]);
}
toleft[k][cen] = A[cen];
for (int rpop = cen + 1; rpop < cen + (1 << k); ++rpop) {
toleft[k][rpop] = Secret(toleft[k][rpop - 1], A[rpop]);
}
}
}
}
int log2C(int n){
int res = 0;
while (n >> 1){
n >>= 1;
res++;
}
return res;
}
int Query(int L, int R) {
if (L == R) return CA[L];
int st = log2C(L ^ R);
return Secret(toright[st][L], toleft[st][R]);
}
