#include <bits/stdc++.h>
#include "mosaic.h"
using namespace std;
#define ll long long
#define all(x) (x).begin(), (x).end()
const int mxn = 2e5 + 100;
ll X[3][mxn], Y[mxn][3], prfX[3][mxn], prfY[mxn][3], prf[2 * mxn];
// x - vertical, y - horizontal
map<pair<int, int>, int> comp;
ll f(int x, int y) {
if (!comp.count({x, y})) {
while (1) {
;
}
}
return comp[{x, y}];
}
pair<ll, int> trim(int x, int y) {
if (y < 0) return {0, -1};
ll res = 0;
for (int i = y; i < 2; i++) {
res += Y[x][i];
}
return {res, max(y, 2)};
}
ll get(int x, int y, int val) {
if (y < 0 || x < 0) return 0;
if (x <= 2) return prfX[x][y];
ll ind = 0;
if (x < y) ind = f(2, y - (x - 2));
else ind = f(x - (y - 2), 2);
if (ind - val < 0) return 0;
return prf[ind - val];
}
ll special(int x, int y1, int y2) {
ll ans = 0;
for (int i = y1; i <= y2; i++) ans += Y[x][i];
return ans;
}
vector<ll> mosaic(vector<int> _X, vector<int> _Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
int n = _X.size();
int q = T.size();
vector<ll> C(q, 0);
for (int i = 0; i < n; i++) {
X[0][i] = _X[i], Y[i][0] = _Y[i];
prfX[0][i] = (i > 0 ? prfX[0][i - 1] : 0) + X[0][i];
prfY[i][0] = (i > 0 ? prfY[i - 1][0] : 0) + Y[i][0];
}
for (int i = 1; i < 3; i++) {
X[i][0] = Y[i][0];
prfX[i][0] = X[i][0];
for (int j = 1; j < n; j++) {
X[i][j] = (!X[i][j - 1] && !X[i - 1][j]);
prfX[i][j] = prfX[i][j - 1] + X[i][j];
}
}
for (int i = 1; i < 3; i++) {
Y[0][i] = X[0][i];
prfY[0][i] = Y[0][i];
for (int j = 1; j < n; j++) {
Y[j][i] = (!Y[j][i - 1] && !Y[j - 1][i]);
prfY[j][i] = prfX[j - 1][i] + Y[j][i];
}
}
int cnt = 0;
for (int i = n - 1; i >= 2; i--) {
prf[cnt] = (cnt > 0 ? prf[cnt - 1] : 0) + Y[i][2];
comp[{i, 2}] = cnt++;
}
for (int i = 3; i < n; i++) {
prf[cnt] = prf[cnt - 1] + X[2][i];
comp[{2, i}] = cnt++;
}
for (int i = 0; i < q; i++) {
if (R[i] <= 2) {
C[i] = special(T[i], L[i], R[i]);
}
else C[i] = trim(T[i], L[i]).first + get(T[i], R[i], 0) - (get(T[i], trim(T[i], L[i]).second, 1));
}
return C;
}
