#include <algorithm>
#include <iostream>
using namespace std;
int Secret(int, int);
const int I = 1024;
int p[10][I], s[10][I], a[I];
int resi(int l, int r, int i, int xl, int xr) {
i--;
int xm = (xl + xr) / 2, y;
// l <= xm, xm+1 <= r
if (xm-1 < l)
y = resi(l, r, i, xm, xr);
else if (xm > r)
y = resi(l, r, i, xl, xm);
else {
// cerr << i << ' ' << xl << ' ' << xr << '\n';
y = Secret(s[i][l], p[i][r]);
}
return y;
}
int Query(int L, int R) {
return R-L ? resi(L, R, 10, 0, 1024) : a[L];
}
void Init(int N, int* A) {
copy(A, A+N, a);
copy(a, a+I, p[0]);
copy(a, a+I, s[0]);
for (int i=1; i<=9; i++) {
int u = 1 << i, v = u / 2;
for (int j=0; j<I; j+=u) {
copy(p[i-1]+j, p[i-1]+j+v, p[i]+j);
copy(s[i-1]+j+v, s[i-1]+j+u, s[i]+j+v);
for (int k=j+v; k<j+u; k++)
p[i][k] = Secret(p[i][k-1], a[k]);
for (int k=j+v; k>j+1; k--)
s[i][k-1] = Secret(a[k-1], s[i][k]);
s[i][j] = p[i][j+u-1];
}
}
}
/*
int main() {
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Init(10, a);
cout << Query(1, 1) << "\n"; // 2
cout << Query(2, 2) << "\n"; // 3
cout << Query(0, 9) << "\n"; // 55
cout << Query(0, 1023) << "\n"; // 55
cout << Query(1, 4) << "\n"; // 14
cout << Query(5, 6) << "\n"; // 13
cout << Query(6, 7) << "\n"; // 15
}
int Secret(int x, int y) {
return x + y;
}
*/
