#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> prod;
void Init(int N, int A[]) {
auto recur = [&] (auto &self, int lg, int l, int r) -> void {
if (lg == (int) prod.size())
prod.emplace_back(N);
if (l == r) {
prod[lg][l] = A[l];
return;
}
int m = (l + r) / 2;
prod[lg][m] = A[m];
for (int i=m-1; i>=l; i--)
prod[lg][i] = Secret(A[i], prod[lg][i+1]);
prod[lg][m+1] = A[m+1];
for (int i=m+2; i<=r; i++)
prod[lg][i] = Secret(prod[lg][i-1], A[i]);
self(self, lg + 1, l, m);
self(self, lg + 1, m + 1, r);
};
n = N;
prod.clear();
recur(recur, 0, 0, N - 1);
}
int Query(int L, int R) {
auto recur = [&] (auto &self, int lg, int l, int r) -> int {
if (l == r)
return prod[lg][l];
int m = (l + r) / 2;
if (L <= m && m < R)
return Secret(prod[lg][L], prod[lg][R]);
if (L <= m && R <= m)
return self(self, lg + 1, l, m);
return self(self, lg + 1, m + 1, r);
};
return recur(recur, 0, 0, n - 1);
}
