#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 2e5 + 5;
int H[4][N], V[N][4], prefH[4][N];
int get(int r, int c) {
if(r < 4) return H[r][c];
if(c < 4) return V[r][c];
if(r <= c) return H[3][c-r+3];
return V[r-c+3][3];
}
pii _map(int r, int c) {
int off = min(r, c)-3;
return { r-off, c-off };
}
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(), q = t.size();
vector<ll> ans(q);
for(int i=0; i<n; i++) {
H[0][i] = x[i];
V[i][0] = y[i];
if(i < 4) H[i][0] = y[i];
if(i < 4) V[0][i] = x[i];
}
for(int i=1; i<4; i++)
for(int j=1; j<n; j++)
H[i][j] = (H[i-1][j] + H[i][j-1] == 0);
for(int j=1; j<4; j++)
for(int i=1; i<n; i++)
V[i][j] = (V[i-1][j] + V[i][j-1] == 0);
for(int i=0; i<4; i++) {
prefH[i][0] = H[i][0];
for(int j=1; j<n; j++)
prefH[i][j] = prefH[i][j-1] + H[i][j];
}
map<pii, int> pos;
vector<int> pref;
int id = 0;
for(int i=n-1; i>=3; i--) {
pref.push_back(V[i][3]);
if(pref.size() > 1) pref.back() += pref[pref.size()-2];
pos[{ i, 3 }] = id++;
}
for(int i=4; i<n; i++) {
pref.push_back(H[3][i]);
if(pref.size() > 1) pref.back() += pref[pref.size()-2];
pos[{ 3, i }] = id++;
}
for(int i=0; i<q; i++) {
int c1 = l[i], c2 = r[i];
int r = t[i];
if(r < 4) {
ans[i] = prefH[r][c2] - (c1 ? prefH[r][c1-1] : 0);
} else {
if(c2 < 4) {
for(int j=c1; j<=c2; j++) ans[i] += V[r][j];
} else {
if(c1 < 4) {
for(int j=c1; j<4; j++) ans[i] += V[r][j];
c1 = 4;
}
int L = pos[_map(r, c1)], R = pos[_map(r, c2)];
ans[i] += pref[R];
if(L) ans[i] -= pref[L-1];
}
}
}
return ans;
}
