#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], prefV[N][4];
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];
}
for(int j=0; j<4; j++) {
prefV[0][j] = V[0][j];
for(int i=1; i<n; i++)
prefV[i][j] = prefV[i-1][j] + V[i][j];
}
map<pii, int> pos;
vector<ll> pref, prefL, prefR;
vector<int> ord;
int id = 0;
for(int i=n-1; i>=3; i--) {
ord.push_back(V[i][3]);
pos[{ i, 3 }] = id++;
}
for(int i=4; i<n; i++) {
ord.push_back(H[3][i]);
pos[{ 3, i }] = id++;
}
pref.push_back(ord[0]);
for(int i=1; i<ord.size(); i++)
pref.push_back(pref.back() + ord[i]);
prefL.push_back(ord[0]);
for(int i=1; i<ord.size(); i++)
prefL.push_back(prefL.back() + ord[i] * (i + 1));
prefR = prefL; prefR.back() = ord.back();
for(int i=ord.size()-2; i>=0; i--)
prefR[i] = prefR[i+1] + ord[i] * (ord.size() - i);
prefR.push_back(0);
for(int i=0; i<q; i++) {
int r1=t[i], r2=b[i], c1=l[i], c2=r[i];
if(r2 < 4) {
for(int j=r1; j<=r2; j++)
ans[i] += prefH[j][c2] - (c1 ? prefH[j][c1-1] : 0);
} else if(c2 < 4) {
for(int j=c1; j<=c2; j++)
ans[i] += prefV[r2][j] - (r1 ? prefV[r1-1][j] : 0);
} else {
if(r1 < 4) {
for(int j=r1; j<4; j++)
ans[i] += prefH[j][c2] - (c1 ? prefH[j][c1-1] : 0);
r1 = 4;
}
if(c1 < 4) {
for(int j=c1; j<4; j++)
ans[i] += prefV[r2][j] - (r1 ? prefV[r1-1][j] : 0);
c1 = 4;
}
int L = pos[_map(r2, c1)], R = pos[_map(r1, c2)];
int mn = min(r2-r1, c2-c1) + 1;
ans[i] += prefL[L+mn-1];
ans[i] -= prefL[L-1];
ans[i] -= (pref[L+mn-1] - pref[L-1]) * (L - 1);
L += mn;
ans[i] += prefR[R-mn+1];
ans[i] -= prefR[R+1];
ans[i] -= (pref[R-mn+1] - pref[R+1]) * (ord.size() - R - 1);
R -= mn;
ans[i] += pref[R] * mn;
ans[i] -= pref[L-1] * mn;
}
}
return ans;
}
