#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
int L[MAXN], R[MAXN], B[MAXN];
int dp[10][MAXN], mask[MAXN];
void dnc(int l, int r, int d) {
if (l == r) return;
int mid = (l + r) / 2;
dp[d][mid] = B[mid], dp[d][mid+1] = B[mid+1];
for (int i = mid-1; i >= l; i--) dp[d][i] = Secret(B[i], dp[d][i+1]);
for (int i = mid+2; i <= r; i++) dp[d][i] = Secret(dp[d][i-1], B[i]);
for (int i = mid+1; i <= r; i++) mask[i] |= (1 << d);
dnc(l, mid, d+1);
dnc(mid+1, r, d+1);
}
void Init(int N, int A[]) {
for (int i = 0; i < N; i++) B[i] = A[i];
dnc(0, N-1, 0);
}
int Query(int L, int R) {
if (L == R) return B[L];
int t = __builtin_ctz(mask[L] ^ mask[R]);
return Secret(dp[t][L], dp[t][R]);
}
