#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
int t[10][1001],msk[1001],b[1001];
void build(int x, int l, int r, int a[])
{
if(l>=r)return;
int mid=(l+r)/2;
t[x][mid]=a[mid];
for(int i=mid-1;i>=l;i--)
t[x][i]=Secret(a[i],t[x][i+1]);
t[x][mid+1]=a[mid+1];
msk[mid+1]|=(1<<x);
for(int i=mid+2;i<=r;i++)
{
t[x][i]=Secret(t[x][i-1],a[i]);
msk[i]|=(1<<x);
}
build(x+1,l,mid,a);
build(x+1,mid+1,r,a);
}
void Init(int n, int a[])
{
for(int i=0;i<n;i++)b[i]=a[i];
build(0,0,n-1,a);
}
int Query(int l, int r)
{
if(l==r) return b[l];
int z=__builtin_ctz(msk[l]^msk[r]);
return Secret(t[z][l],t[z][r]);
}
