#include "mosaic.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ALL(x) (x.begin()), (x.end())
#define DEBUG(x) cerr << #x << ": " << x << endl;
#define DEBUG_ARR(x) /*{ cerr << #x << ": "; { for (auto &y : x) cout << y << " "; cout << endl; } }*/
#define SZ(x) ((int)x.size())
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> L, std::vector<int> R) {
int q = SZ(T);
int n = SZ(X);
{
vvl a(n, vl(n));
for (int i = 0; i < n; i++) a[i][0] = Y[i], a[0][i] = X[i];
for (int i = 0; i < n-1; i++) for (int j = 0; j < n-1; j++) {
int k = a[i][j+1] + a[i+1][j];
a[i+1][j+1] = (k == 0);
}
for (int i = 0; i < n; i++) DEBUG_ARR(a[i]);
}
vl ans(q);
vvi rows(3, vi(n)), cols(3, vi(n));
for (int i = 0; i < n; i++) rows[0][i] = X[i], cols[0][i] = Y[i];
rows[1][0] = cols[0][1];
rows[2][0] = cols[0][2];
cols[1][0] = rows[0][1];
cols[2][0] = rows[0][2];
for (int i = 1; i < 3; i++) {
for (int j = 1; j < n; j++) {
int k = rows[i-1][j]+rows[i][j-1];
rows[i][j] = (k == 0);
k = cols[i-1][j]+cols[i][j-1];
cols[i][j] = (k == 0);
}
}
vvi prefr(3, vi(n+1)), prefc(3, vi(n+1));
for (int i = 0; i < 3; i++) for (int j = 0; j < n; j++) {
prefr[i][j+1] = prefr[i][j]+rows[i][j];
prefc[i][j+1] = prefc[i][j]+cols[i][j];
}
for (auto r : rows) DEBUG_ARR(r);
for (auto c : cols) DEBUG_ARR(c);
vi b;
for (int i = n-1; i >= 3; i--) b.push_back(cols[2][i]);
for (int i = 2; i < n; i++) b.push_back(rows[2][i]);
DEBUG_ARR(b);
vl prefb(SZ(b)+1);
for (int i = 0; i < SZ(b); i++) prefb[i+1] = prefb[i]+b[i];
vl prefli(SZ(b)+1);
for (int i = 0; i < SZ(b); i++) prefli[i+1] = prefli[i]+b[i]*(i+1);
vl prefri(SZ(b)+1);
for (int i = 0; i < SZ(b); i++) prefri[SZ(b)-1-i] = prefri[SZ(b)-i]+b[SZ(b)-1-i]*(i+1);
DEBUG_ARR(prefli);
DEBUG_ARR(prefri);
for (int t = 0; t < q; t++) {
int xl = L[t], xr = R[t], yt = T[t], yb = B[t];
if (yb < 3) {
for (int i = yt; i <= yb; i++) ans[t] += prefr[i][xr+1]-prefr[i][xl];
continue;
}
if (xr < 3) {
for (int i = xl; i <= xr; i++) ans[t] += prefc[i][yb+1]-prefc[i][yt];
continue;
}
while (xl < 3) {
ans[t] += prefc[xl][yb+1]-prefc[xl][yt];
xl++;
}
while (yt < 3) {
ans[t] += prefr[yt][xr+1]-prefr[yt][xl];
yt++;
}
int y = n-1-yt;
int l = xl+y-2;
int r = xr+y-2;
l -= yb-yt;
int w = xr-xl+1, h = yb-yt+1;
int mn = min(w, h);
int lm = l+mn-1;
int rm = r-mn+1;
ans[t] += prefli[lm]-prefli[l];
ans[t] += prefri[rm]-prefri[r];
ans[t] += (prefb[rm+1]-prefb[lm])*mn;
}
return ans;
}
