#include <bits/stdc++.h>
using namespace std;
vector<long long> mosaic(
vector<int> X, vector<int> Y,
vector<int> T, vector<int> B,
vector<int> L, vector<int> R
) {
int N = (int)X.size();
int Q = (int)T.size();
vector<int> row1(N, 0), col1(N, 0), row2(N, 0), col2(N, 0);
// Build row 1 and column 1
if (N >= 2) {
row1[0] = Y[1];
for (int j = 1; j < N; ++j) {
row1[j] = (X[j] == 0 && row1[j - 1] == 0) ? 1 : 0;
}
col1[0] = X[1];
for (int i = 1; i < N; ++i) {
col1[i] = (col1[i - 1] == 0 && Y[i] == 0) ? 1 : 0;
}
}
// Build row 2 and column 2
if (N >= 3) {
row2[0] = Y[2];
row2[1] = (row1[1] == 0 && row2[0] == 0) ? 1 : 0;
for (int j = 2; j < N; ++j) {
row2[j] = (row1[j] == 0 && row2[j - 1] == 0) ? 1 : 0;
}
col2[0] = X[2];
col2[1] = (col2[0] == 0 && col1[1] == 0) ? 1 : 0;
for (int i = 2; i < N; ++i) {
col2[i] = (col2[i - 1] == 0 && col1[i] == 0) ? 1 : 0;
}
}
// Prefix sums on row 0, row 1
vector<long long> prefRow0(N, 0), prefRow1(N, 0);
if (N > 0) {
long long s = 0;
for (int j = 0; j < N; ++j) {
s += X[j];
prefRow0[j] = s;
}
s = 0;
for (int j = 0; j < N; ++j) {
s += row1[j];
prefRow1[j] = s;
}
}
// Prefix sums on col 0, col 1
vector<long long> prefCol0(N, 0), prefCol1(N, 0);
if (N > 0) {
long long s = 0;
for (int i = 0; i < N; ++i) {
s += Y[i];
prefCol0[i] = s;
}
s = 0;
for (int i = 0; i < N; ++i) {
s += col1[i];
prefCol1[i] = s;
}
}
// Z[d] for d in [-(N-3), ..., (N-3)]
int M = N - 3; // if M < 0, no inner (i>=2,j>=2) core exists
vector<long long> ps0, ps1; // prefix of Z, prefix of d*Z
if (M >= 0) {
int len = 2 * M + 1;
ps0.assign(len + 1, 0);
ps1.assign(len + 1, 0);
for (int idx = 0; idx < len; ++idx) {
int d = idx - M;
int val = (d >= 0) ? row2[2 + d] : col2[2 - d];
ps0[idx + 1] = ps0[idx] + val;
ps1[idx + 1] = ps1[idx] + 1LL * val * d;
}
}
auto sumRangePS = [&](const vector<long long>& ps, int lo, int hi) -> long long {
if (M < 0 || lo > hi) return 0;
lo = max(lo, -M);
hi = min(hi, M);
if (lo > hi) return 0;
int Lidx = lo + M;
int Ridx = hi + M;
return ps[Ridx + 1] - ps[Lidx];
};
auto sumLinear = [&](int lo, int hi, long long a, long long b) -> long long {
// sum_{d=lo..hi} Z[d] * (a*d + b)
if (lo > hi) return 0;
long long S0 = sumRangePS(ps0, lo, hi);
long long S1 = sumRangePS(ps1, lo, hi);
return a * S1 + b * S0;
};
auto coreSum = [&](int t, int b, int l, int r) -> long long {
// sum on rectangle [t..b] x [l..r], assuming t>=2 and l>=2
if (M < 0 || t > b || l > r) return 0;
long long h = b - t + 1;
long long w = r - l + 1;
int d0 = l - b;
int d1 = l - t;
int d2 = r - b;
int d3 = r - t;
int x = min(d1, d2);
int y = max(d1, d2);
long long m = min(h, w);
long long ans = 0;
// Increasing part: cnt(d) = d - d0 + 1
ans += sumLinear(d0, x, 1, 1LL - d0);
// Plateau: cnt(d) = m
ans += sumLinear(x + 1, y, 0, m);
// Decreasing part: cnt(d) = d3 - d + 1
ans += sumLinear(y + 1, d3, -1, 1LL * d3 + 1);
return ans;
};
auto rowRange = [&](const vector<long long>& pref, int l, int r) -> long long {
if (l > r) return 0;
long long res = pref[r];
if (l > 0) res -= pref[l - 1];
return res;
};
auto colRange = [&](const vector<long long>& pref, int t, int b) -> long long {
if (t > b) return 0;
long long res = pref[b];
if (t > 0) res -= pref[t - 1];
return res;
};
vector<long long> C(Q, 0);
for (int k = 0; k < Q; ++k) {
int t = T[k], b = B[k], l = L[k], r = R[k];
long long ans = 0;
// Part 1: rows 0 and 1
int rb = min(b, 1);
for (int i = t; i <= rb; ++i) {
if (i == 0) ans += rowRange(prefRow0, l, r);
else ans += rowRange(prefRow1, l, r);
}
// Parts with rows >= 2
int t2 = max(t, 2);
if (t2 <= b) {
// Part 2: columns 0 and 1
int cmax = min(r, 1);
for (int j = l; j <= cmax; ++j) {
if (j == 0) ans += colRange(prefCol0, t2, b);
else ans += colRange(prefCol1, t2, b);
}
// Part 3: inner core i>=2, j>=2
int l2 = max(l, 2);
if (l2 <= r) {
ans += coreSum(t2, b, l2, r);
}
}
C[k] = ans;
}
return C;
}
