#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1005;
int n;
int c[mxN];
int g[mxN][20]; // g[i][k]：在第 k 層分治時，i 點對應的累積值
void dc(int l, int r, int k) {
if (l == r) return;
int mid = (l + r) / 2;
// 左邊累積
g[mid][k] = c[mid];
for (int i = mid - 1; i >= l; i--) {
g[i][k] = Secret(c[i], g[i + 1][k]);
}
// 右邊累積
g[mid + 1][k] = c[mid + 1];
for (int i = mid + 2; i <= r; i++) {
g[i][k] = Secret(g[i - 1][k], c[i]);
}
dc(l, mid, k + 1);
dc(mid + 1, r, k + 1);
}
void Init(int N, int A[]) {
n = N;
for (int i = 0; i < N; i++) c[i] = A[i];
dc(0, n - 1, 0); // 從第 0 層開始
}
int qry(int k, int l, int r, int L, int R) {
int mid = (L + R) / 2;
if (l <= mid && r > mid) {
return Secret(g[l][k], g[r][k]);
}
if (r <= mid) return qry(k + 1, l, r, L, mid);
if (l > mid) return qry(k + 1, l, r, mid + 1, R);
return -1; // safety
}
int Query(int L, int R) {
if (L == R) return c[L];
return qry(0, L, R, 0, n - 1);
}
