#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<long long> result(Q);
// Prefix sums for the first row and first column
vector<long long> prefX(N + 1, 0), prefY(N + 1, 0);
for (int i = 0; i < N; i++) {
prefX[i + 1] = prefX[i] + X[i];
prefY[i + 1] = prefY[i] + Y[i];
}
// Layer 1 sequences (row and column parts)
int n1 = N >= 1 ? N - 1 : 0;
vector<int> rowSeq1(n1, 0);
vector<long long> prefixRow1(n1 + 1, 0);
if (n1 > 0) {
rowSeq1[0] = (X[1] == 0 && Y[1] == 0) ? 1 : 0;
for (int k = 1; k < n1; k++) {
rowSeq1[k] = (rowSeq1[k - 1] == 0 && X[k + 1] == 0) ? 1 : 0;
}
for (int i = 0; i < n1; i++) prefixRow1[i + 1] = prefixRow1[i] + rowSeq1[i];
}
int n_c1 = N >= 2 ? N - 2 : 0;
vector<int> colSeq1(n_c1, 0);
vector<long long> prefixCol1(n_c1 + 1, 0);
if (n_c1 > 0) {
colSeq1[0] = (rowSeq1[0] == 0 && Y[2] == 0) ? 1 : 0;
for (int k = 1; k < n_c1; k++) {
colSeq1[k] = (colSeq1[k - 1] == 0 && Y[k + 2] == 0) ? 1 : 0;
}
for (int i = 0; i < n_c1; i++) prefixCol1[i + 1] = prefixCol1[i] + colSeq1[i];
}
// Layer 2 sequences (row and column parts)
int n2 = N >= 2 ? N - 2 : 0;
vector<int> rowSeq2(n2, 0);
vector<long long> prefixRow2(n2 + 1, 0), sumPrefixRow2(n2 + 2, 0);
if (n2 > 0) {
rowSeq2[0] = (rowSeq1[1] == 0 && colSeq1[0] == 0) ? 1 : 0;
for (int k = 1; k < n2; k++) {
rowSeq2[k] = (rowSeq1[k + 1] == 0 && rowSeq2[k - 1] == 0) ? 1 : 0;
}
for (int i = 0; i < n2; i++) {
prefixRow2[i + 1] = prefixRow2[i] + rowSeq2[i];
}
for (int i = 0; i <= n2; i++) {
sumPrefixRow2[i + 1] = sumPrefixRow2[i] + prefixRow2[i];
}
}
int n3 = N >= 3 ? N - 3 : 0;
vector<int> colSeq2(n3, 0);
vector<long long> prefixCol2(n3 + 1, 0), sumPrefixCol2(n3 + 2, 0);
if (n3 > 0) {
colSeq2[0] = (rowSeq2[0] == 0 && colSeq1[1] == 0) ? 1 : 0;
for (int k = 1; k < n3; k++) {
colSeq2[k] = (colSeq2[k - 1] == 0 && colSeq1[k + 1] == 0) ? 1 : 0;
}
for (int i = 0; i < n3; i++) {
prefixCol2[i + 1] = prefixCol2[i] + colSeq2[i];
}
for (int i = 0; i <= n3; i++) {
sumPrefixCol2[i + 1] = sumPrefixCol2[i] + prefixCol2[i];
}
}
for (int qi = 0; qi < Q; qi++) {
int t = T[qi], b = B[qi], lq = L[qi], rq = R[qi];
long long total = 0;
// Layer 0: row and column 0
if (t <= 0 && 0 <= b) {
int sj = max(lq, 0), ej = rq;
if (sj <= ej) total += prefX[ej + 1] - prefX[sj];
}
if (lq <= 0 && 0 <= rq) {
int si = max(t, 1), ei = b;
if (si <= ei) total += prefY[ei + 1] - prefY[si];
}
// Layer 1: row 1, col >=1 and col 1, row >=2
if (n1 > 0 && t <= 1 && 1 <= b && rq >= 1) {
int ks = max(lq, 1) - 1;
int ke = min(rq - 1, n1 - 1);
if (ks <= ke) total += prefixRow1[ke + 1] - prefixRow1[ks];
}
if (n_c1 > 0 && lq <= 1 && 1 <= rq && b >= 2) {
int is_ = max(t, 2);
int ie = b;
int ks = is_ - 2;
int ke = min(ie - 2, n_c1 - 1);
if (ks <= ke) total += prefixCol1[ke + 1] - prefixCol1[ks];
}
// Layers >=2: row parts
if (n2 > 0 && rq >= 2 && b >= 2) {
int ls = max(2, t), le = min(b, rq);
if (ls <= le) {
int i_start = rq - le + 1;
int i_end = rq - ls + 1;
long long sumEnd = sumPrefixRow2[i_end + 1] - sumPrefixRow2[i_start];
int leftEnd = min(le, lq);
long long sumStart = 0;
if (leftEnd >= ls) {
int a = lq - leftEnd;
int z = lq - ls;
sumStart = sumPrefixRow2[z + 1] - sumPrefixRow2[a];
}
total += sumEnd - sumStart;
}
}
// Layers >=2: column parts
if (n3 > 0 && rq >= 2 && b >= 3) {
int ls = max(2, lq);
int le = min(rq, b - 1);
if (ls <= le) {
int i_start = b - le;
int i_end = b - ls;
long long sumEnd = sumPrefixCol2[i_end + 1] - sumPrefixCol2[i_start];
int lowEnd = min(le, t - 1);
long long sumStart = 0;
if (lowEnd >= ls) {
int a = t - lowEnd - 1;
int z = t - ls - 1;
if (z >= 0) {
int A = max(0, a);
sumStart = sumPrefixCol2[z + 1] - sumPrefixCol2[A];
}
}
total += sumEnd - sumStart;
}
}
result[qi] = total;
}
return result;
}
