#include "secret.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rng(i,s,n) for(ll i = (s) ; i < (n) ; i++)
#define rep(i,n) rng(i, 0, (n))
#define vec vector
#define pb emplace_back
#define siz(a) (int)(a).size()
vec<ll>a;
class dsp{
int n,rr;
vec<vec<ll>>dat;
vec<int>lgt;
public:
void init(int sz){
n=sz;
int cnt=1;//バケットサイズ
while((1<<cnt)<n) cnt++;
dat.assign(cnt,vec<ll>(n,0));
rep(i,n) dat[0][i]=a[i];
rng(k,1,cnt){
for(int j=0;j+(1<<k)<n;j+=(1<<(k+1))){
int t=j+(1<<k);
dat[k][t-1]=a[t-1],dat[k][t]=a[t];
for(int r=t-2;r>=j;r--){
dat[k][r]=Secret(a[r],dat[k][r+1]);
}
for(int r=t+1;r<j+(1<<(k+1));r++){
dat[k][r]=Secret(dat[k][r-1],a[r]);
}
}
}
lgt.assign((1<<cnt),0);
for(int i=2;i<n+10;i++) lgt[i]=lgt[i>>1]+1;
}
int query(int x,int y){
if(x==y) return dat[0][x];
int k=lgt[x^y];
return Secret(dat[k][x],dat[k][y]);
}
} dsp;
void Init(int N, int A[]) {
rep(i,N) a.pb(A[i]);
dsp.init(N);
}
int Query(int L, int R) {
int k=dsp.query(L,R);
return k;
}
