#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
struct GridSolver {
int N;
// S0[i]: Prefix sum of V[k]
// S1[i]: Prefix sum of k * V[k]
// Indices are offset by N to handle negative diagonal indices.
// Index i corresponds to diagonal k = i - N.
vector<ll> S0, S1;
// Prefix sums for input arrays X (Row 0) and Y (Col 0)
vector<ll> PX, PY;
void build(int n, const vector<int>& X, const vector<int>& Y) {
N = n;
// --- Step 1: Compute Row 1 and Column 1 ---
// These serve as the "generators" for the rest of the grid (i,j >= 1).
vector<int> R1(N), C1(N);
// Only proceed if N > 1, as the inner grid exists only for N >= 2
if (N > 1) {
// Compute corner (1,1). Logic: NOR(Top, Left) -> NOR(X[1], Y[1])
int val_1_1 = ((X[1] == 0) && (Y[1] == 0)) ? 1 : 0;
R1[1] = val_1_1;
C1[1] = val_1_1;
// Fill Row 1
for (int j = 2; j < N; ++j) {
// Top is X[j], Left is R1[j-1]
R1[j] = ((X[j] == 0) && (R1[j-1] == 0)) ? 1 : 0;
}
// Fill Column 1
for (int i = 2; i < N; ++i) {
// Top is C1[i-1], Left is Y[i]
C1[i] = ((C1[i-1] == 0) && (Y[i] == 0)) ? 1 : 0;
}
}
// --- Step 2: Build Diagonal Value Array V ---
// V[k] stores the value for diagonal j - i = k.
// Valid k for inner grid ranges from -(N-2) to (N-2).
// To cover all potential query ranges safely, we size for roughly -N to N.
int offset = N;
int v_size = 2 * N + 5;
vector<int> V(v_size, 0);
if (N > 1) {
// k=0 corresponds to (1,1)
V[0 + offset] = R1[1];
// k > 0: Upper triangular part (Row 1). k goes up to N-2.
for (int k = 1; k < N; ++k) {
if (1 + k < N) V[k + offset] = R1[1+k];
}
// k < 0: Lower triangular part (Col 1). k goes down to -(N-2).
for (int k = -1; k > -N; --k) {
if (1 - k < N) V[k + offset] = C1[1-k];
}
}
// --- Step 3: Compute Prefix Sums for Diagonals ---
S0.assign(v_size, 0);
S1.assign(v_size, 0);
for (int i = 0; i < v_size; ++i) {
ll val = V[i];
ll prev0 = (i > 0) ? S0[i-1] : 0;
ll prev1 = (i > 0) ? S1[i-1] : 0;
ll k = i - offset; // Actual diagonal index
S0[i] = prev0 + val;
S1[i] = prev1 + k * val;
}
// --- Step 4: Prefix Sums for Boundaries (Row 0, Col 0) ---
PX.assign(N, 0);
PY.assign(N, 0);
PX[0] = X[0];
for(int i=1; i<N; ++i) PX[i] = PX[i-1] + X[i];
PY[0] = Y[0];
for(int i=1; i<N; ++i) PY[i] = PY[i-1] + Y[i];
}
// Helper: Range sum for S0. range [k1, k2] inclusive.
ll get_S0(int k1, int k2) {
int offset = N;
int i1 = k1 + offset;
int i2 = k2 + offset;
if (i1 > i2) return 0;
// Clamp indices to the stored range.
// V is effectively 0 outside valid indices, so this is safe.
i1 = max(0, i1);
i2 = min((int)S0.size()-1, i2);
if (i1 > i2) return 0; // Double check after clamping
ll v2 = S0[i2];
ll v1 = (i1 > 0) ? S0[i1-1] : 0;
return v2 - v1;
}
// Helper: Range sum for S1. range [k1, k2] inclusive.
ll get_S1(int k1, int k2) {
int offset = N;
int i1 = k1 + offset;
int i2 = k2 + offset;
if (i1 > i2) return 0;
i1 = max(0, i1);
i2 = min((int)S1.size()-1, i2);
if (i1 > i2) return 0;
ll v2 = S1[i2];
ll v1 = (i1 > 0) ? S1[i1-1] : 0;
return v2 - v1;
}
// Calculates sum of black tiles in the global rectangle defined by corner (rows, cols)
// relative to the inner grid start.
// Effectively sums V[c-r] for 1 <= r <= rows, 1 <= c <= cols.
ll calc_grid_sum(int rows, int cols) {
if (rows <= 0 || cols <= 0) return 0;
ll total = 0;
// We split the summation of count(k) * V[k] into 3 linear zones.
if (rows <= cols) {
// Zone 1: Ascending count (bottom-left triangle)
// Range: [1-rows, 0]. Count = rows + k
total += (ll)rows * get_S0(1-rows, 0) + get_S1(1-rows, 0);
// Zone 2: Constant count (middle trapezoid)
// Range: [1, cols-rows]. Count = rows
total += (ll)rows * get_S0(1, cols-rows);
// Zone 3: Descending count (top-right triangle)
// Range: [cols-rows+1, cols-1]. Count = cols - k
total += (ll)cols * get_S0(cols-rows+1, cols-1) - get_S1(cols-rows+1, cols-1);
} else {
// Zone 1: Ascending count
// Range: [1-rows, cols-rows]. Count = rows + k
total += (ll)rows * get_S0(1-rows, cols-rows) + get_S1(1-rows, cols-rows);
// Zone 2: Constant count
// Range: [cols-rows+1, 0]. Count = cols
total += (ll)cols * get_S0(cols-rows+1, 0);
// Zone 3: Descending count
// Range: [1, cols-1]. Count = cols - k
total += (ll)cols * get_S0(1, cols-1) - get_S1(1, cols-1);
}
return total;
}
ll query_X(int L, int R) {
if (L > R) return 0;
ll v2 = PX[R];
ll v1 = (L > 0) ? PX[L-1] : 0;
return v2 - v1;
}
ll query_Y(int T, int B) {
if (T > B) return 0;
ll v2 = PY[B];
ll v1 = (T > 0) ? PY[T-1] : 0;
return v2 - v1;
}
};
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 N = X.size();
int Q = T.size();
GridSolver solver;
solver.build(N, X, Y);
std::vector<long long> results(Q);
for (int k = 0; k < Q; ++k) {
int t = T[k];
int b = B[k];
int l = L[k];
int r = R[k];
ll ans = 0;
// Part A: Intersection with Row 0
if (t == 0) {
ans += solver.query_X(l, r);
}
// Part B: Intersection with Col 0
// We must avoid double counting (0,0) if it was included in Part A.
// If Part A ran (t=0), then (0,0) is counted if l=0.
// We simply take the column sum from row max(1, t) to b.
if (l == 0) {
int y_start = max(1, t);
if (y_start <= b) {
ans += solver.query_Y(y_start, b);
}
}
// Part C: Intersection with Inner Grid (rows 1..N-1, cols 1..N-1)
int t_prime = max(1, t);
int l_prime = max(1, l);
if (t_prime <= b && l_prime <= r) {
// calc_grid_sum(rows, cols) sums the rectangle of size rows x cols starting at inner (1,1).
// This maps to global range [1, rows] x [1, cols].
// We want global range [t_prime, b] x [l_prime, r].
ans += solver.calc_grid_sum(b, r)
- solver.calc_grid_sum(t_prime - 1, r)
- solver.calc_grid_sum(b, l_prime - 1)
+ solver.calc_grid_sum(t_prime - 1, l_prime - 1);
}
results[k] = ans;
}
return results;
}
