#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> dnc(10, vector<int>(1000));
vector<vector<int>> cnd(10, vector<int>(1000));
void divide(int l, int r, int v, int *a) {
if (l == r) dnc[v][l] = a[l];
else {
int m = (l + r) / 2;
divide(l, m, v + 1, a);
divide(m + 1, r, v + 1, a);
dnc[v][l] = a[l];
for (int i = l + 1; i <= m; i++) dnc[v][i] = Secret(dnc[v][i - 1], a[i]);
dnc[v][m + 1] = a[m + 1];
for (int i = m + 2; i <= r; i++) dnc[v][i] = Secret(dnc[v][i - 1], a[i]);
cnd[v][m] = a[m];
for (int i = m - 1; i >= l; i--) cnd[v][i] = Secret(a[i], cnd[v][i + 1]);
cnd[v][r] = a[r];
for (int i = r - 1; i > m; i--) cnd[v][i] = Secret(a[i], cnd[v][i + 1]);
}
}
int nn;
int conquer(int ll, int rr, int l, int r, int v) {
// cout << "dividng " << l << " " << r << endl;
if (l == r) return dnc[v][l];
int m = (l + r) / 2;
if (rr <= m) return conquer(ll, rr, l, m, v + 1);
else if (ll > m) return conquer(ll, rr, m + 1, r, v + 1);
return Secret(cnd[v][ll], dnc[v][rr]);
}
void Init(int n, int a[]) {
nn = n;
divide(0, n - 1, 0, a);
}
int Query(int l, int r) {
// cout << "query" << endl;
return conquer(l, r, 0, nn - 1, 0);
}
