#include "secret.h"
# include <bits/stdc++.h>
# define ll long long
# define vi vector<int>
# define pb push_back
# define pii pair<int, int>
# define fi first
# define se second
using namespace std;
int n, a[1005], val[51], gt[51][51], gtur[51][1005], gtul[51][1005];
const int BLO=20;
void Init(int N, int A[]) {
n=N;
for(int i=0; i<n; i++) a[i]=A[i];
for(int i=1; i<=50; i++) {
if((i-1)*BLO>n) break;
int idx=(i-1)*BLO;
int tmp=a[idx];
gtur[i][idx]=a[idx];
for(int j=idx+1; j<min(n, idx+BLO); j++) {
int tm=Secret(tmp, a[j]);
gtur[i][j]=tm;
tmp=tm;
}
val[i]=tmp;
// cout << "i " << i << " : " << tmp << endl;
if(BLO*i<=n) {
int tmp=a[idx+BLO-1];
gtul[i][idx+BLO-1]=tmp;
for(int j=idx+BLO-2; j>=idx; j--) {
gtul[i][j]=Secret(a[j], tmp);
tmp=gtul[i][j];
}
}
}
for(int i=1; i<=50; i++) {
gt[i][i]=val[i];
for(int j=i+1; j<=50; j++) {
gt[i][j]=Secret(gt[i][j-1], val[j]);
}
}
}
int Query(int L, int R) {
if((R-L+1)<=BLO) {
int tmp=a[L];
for(int j=L+1; j<=R; j++) {
int tm=Secret(tmp, a[j]);
tmp=tm;
}
return tmp;
}
int idx1=(L+BLO)/BLO + 1, idx2=(R+BLO)/BLO-1;
// cout << "idx " << idx1 << " " << idx2 << endl;
// cout << "gtu " << gtul[idx1-1][L] << " " << gtur[idx2+1][R] << " " << gt[idx1][idx2] << endl;
int tmp=gtul[idx1-1][L];
if(idx1<=idx2) {
int tmpp=Secret(tmp, gt[idx1][idx2]);
tmp=tmpp;
}
int tmpp=Secret(tmp, gtur[idx2+1][R]);
return tmpp;
}
