#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[25][1005], gtul[25][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];
for(int j=idx+1; j<min(n, idx+BLO-1); j++) {
int tm=Secret(tmp, a[j]);
gtur[i][j]=tm;
tmp=tm;
}
if(BLO*i<=n) {
int tmp=a[idx+BLO-1];
for(int j=idx+BLO-2; j>=idx; j--) {
gtul[i][j]=Secret(tmp, a[j]);
tmp=gtul[i][j];
}
}
val[i]=tmp;
}
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)<=21) {
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-1)/BLO + 1, idx2=(R+BLO-1)/BLO-1;
int tmp=Secret(gtul[idx1-1][L], gtur[idx2+1][R]);
if(idx1<=idx2) tmp=Secret(tmp, gt[idx1][idx2]);
return tmp;
}
