#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#include "secret.h"
using namespace std;
const int N = 2e3 + 7;
const int LOG = 20;
const int MOD = 1e9 + 7; // 998244353;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;
typedef long long ll;
typedef unsigned long long ull;
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
int n;
int a[N];
int mask[N];
int f[LOG + 1][N];
void compute(int l, int r, int level) {
if (l >= r) return;
int m = (l + r) >> 1;
f[level][m] = a[m];
for (int i = m - 1; i >= l; i --)
f[level][i] = Secret(f[level][i + 1], a[i]);
f[level][m + 1] = a[m + 1];
for (int i = m + 2; i <= r; i ++)
f[level][i] = Secret(f[level][i - 1], a[i]);
for (int i = m + 1; i <= r; i ++) mask[i] ^= (1 << level);
compute(l, m, level + 1);
compute(m + 1, r, level + 1);
}
void Init(int N, int A[]) {
n = N;
for (int i = 1; i <= n; i ++) a[i] = A[i - 1];
compute(1, n, 0);
}
int Query(int l, int r) {
l ++; r ++;
if (l == r) return a[r];
if (r - l == 1) return Secret(a[l], a[r]);
int bit = __builtin_ctz(mask[l] ^ mask[r]);
return Secret(f[bit][l], f[bit][r]);
}
