#include <bits/stdc++.h>
#include "secret.h"
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;
const int mn = 1e3 + 5, inf = 1e9;
int n, a[mn];
// int Secret(int a, int b){
// }
struct Node{
vector <int> prefix, suffix;
Node operator+(const Node& other) const{
Node res;
int n1 = prefix.size(), n2 = other.prefix.size();
res.prefix.resize(n1 + n2);
res.suffix.resize(n1 + n2);
for(int i = 0; i < n1; i++) res.prefix[i] = prefix[i];
for(int i = 0; i < n2; i++) res.prefix[n1 + i] = Secret(prefix.back(), other.prefix[i]);
for(int i = 0; i < n2; i++) res.suffix[n1 + i] = other.suffix[i];
for(int i = n1 - 1; i >= 0; i--) res.suffix[i] = Secret(suffix[i], other.suffix[0]);
return res;
}
} st[mn << 2];
void build(int id, int l, int r){
if(l == r){
st[id].prefix.push_back(a[l]);
st[id].suffix.push_back(a[r]);
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
st[id] = st[id << 1] + st[id << 1 | 1];
}
int get(int id, int l, int r, int u, int v){
if(l == r) return a[l];
int mid = (l + r) >> 1;
if(v <= mid) return get(id << 1, l, mid, u, v);
else if(u > mid) return get(id << 1 | 1, mid + 1, r, u, v);
return Secret(st[id << 1].suffix[u - l], st[id << 1 | 1].prefix[v - mid - 1]);
}
void Init(int N, int A[]){
n = N;
for(int i = 0; i < N; i ++) a[i + 1] = A[i];
build(1, 1, n);
}
int Query(int L, int R){
L ++, R ++;
return get(1, 1, n, L, R);
}
