// Starcraft 2 enjoyer //
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
#define LSOne(X) ((X) & -(X))
const int N = 1e3 + 5;
const int M = 1e6 + 5;
const int LG = 20;
const int C = 26;
const long long INF = 1e9;
const int B = 320;
const int P = 31;
const int MOD = 1e9 + 7;
int n, q, a[N], val[10][N], inp, mask[N];
void build(int l, int r, int lvl)
{
if (l > r)
return;
if (l == r)
{
val[lvl][l] = a[l];
return;
}
int m = (l + r) / 2;
val[lvl][m] = a[m];
for (int x = m - 1; x >= l; x--)
{
inp = Secret(val[lvl][x + 1], a[x]);
// inp = val[lvl][x + 1] + a[x];
val[lvl][x] = inp;
}
if (m + 1 <= r)
val[lvl][m + 1] = a[m + 1];
for (int x = m + 2; x <= r; x++)
{
inp = Secret(val[lvl][x - 1], a[x]);
// inp = val[lvl][x - 1] + a[x];
val[lvl][x] = inp;
}
for (int x = m + 1; x <= r; x++)
{
mask[x] ^= 1 << lvl;
}
build(l, m, lvl + 1);
build(m + 1, r, lvl + 1);
}
void Init(int N, int A[])
{
n = N;
for (int x = 0; x < n; x++)
{
a[x] = A[x];
}
build(0, n - 1, 0);
}
int Query(int l, int r)
{
if (l == r)
{
return a[l];
}
int i = __builtin_ctz(mask[l] ^ mask[r]);
inp = Secret(val[i][l], val[i][r]);
// inp = val[i][l] + val[i][r];
return inp;
}
