#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// We use long long for sums to avoid overflow (N*N can be 4*10^10)
typedef long long ll;
struct GridSolver {
int N;
// Prefix sums for the diagonal values
// S0[k] = sum of V[i] for i <= k
// S1[k] = sum of i * V[i] for i <= k
// Indices for V range from -(N-1) to (N-1).
// We offset them by adding N.
vector<ll> S0, S1;
// Prefix sums for Row 0 and Col 0
vector<int> PX, PY;
void build(int n, const vector<int>& X, const vector<int>& Y) {
N = n;
// 1. Compute Row 1 and Col 1 values (for the grid starting at 1,1)
// Global (1, j) depends on Global (0, j) and Global (1, j-1)
// Global (i, 1) depends on Global (i-1, 1) and Global (i, 0)
vector<int> R1(N), C1(N);
// Compute (1, 1)
int val_1_1 = ((X[1] == 0) && (Y[1] == 0)) ? 1 : 0;
R1[1] = val_1_1;
C1[1] = val_1_1;
for (int j = 2; j < N; ++j) {
R1[j] = ((X[j] == 0) && (R1[j-1] == 0)) ? 1 : 0;
}
for (int i = 2; i < N; ++i) {
C1[i] = ((C1[i-1] == 0) && (Y[i] == 0)) ? 1 : 0;
}
// 2. Build V array
// V[k] corresponds to diagonal c - r = k
// range of k: -(N-1) to (N-1)
// Size needed: 2*N
int offset = N;
int v_size = 2 * N + 5;
vector<int> V(v_size, 0);
// Center k=0 is (1,1) -> R1[1]
V[0 + offset] = R1[1];
// Positive k: (1, 1+k) -> R1[1+k]
for (int k = 1; k < N; ++k) {
if (1 + k < N) V[k + offset] = R1[1+k];
}
// Negative k: (1-k, 1) -> C1[1-k]. Let k = -d. (1+d, 1) -> C1[1+d]
for (int k = -1; k > -N; --k) {
if (1 - k < N) V[k + offset] = C1[1-k];
}
// 3. Build Prefix Sums
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;
// The actual k value is (i - offset)
ll k = i - offset;
S0[i] = prev0 + val;
S1[i] = prev1 + k * val;
}
// 4. Prefix sums for X and Y
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];
}
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 just in case, though logic should prevent OOB
i1 = max(0, i1);
i2 = min((int)S0.size()-1, i2);
ll v2 = S0[i2];
ll v1 = (i1 > 0) ? S0[i1-1] : 0;
return v2 - v1;
}
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);
ll v2 = S1[i2];
ll v1 = (i1 > 0) ? S1[i1-1] : 0;
return v2 - v1;
}
// Calculate sum of diagonals in global rect [1..rows] x [1..cols]
// Note: rows, cols are counts.
// e.g. rows=2 means global rows 1 and 2 are included.
ll calc_grid_sum(int rows, int cols) {
if (rows <= 0 || cols <= 0) return 0;
ll total = 0;
if (rows <= cols) {
// Zone 1: [1-rows, 0]. Count = rows + k
total += (ll)rows * get_S0(1-rows, 0) + get_S1(1-rows, 0);
// Zone 2: [1, cols-rows]. Count = rows
total += (ll)rows * get_S0(1, cols-rows);
// Zone 3: [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: [1-rows, cols-rows]. Count = rows + k
total += (ll)rows * get_S0(1-rows, cols-rows) + get_S1(1-rows, cols-rows);
// Zone 2: [cols-rows+1, 0]. Count = cols
total += (ll)cols * get_S0(cols-rows+1, 0);
// Zone 3: [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;
}
};
vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
int N = X.size();
int Q = T.size();
GridSolver solver;
solver.build(N, X, Y);
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: Row 0
if (t == 0) {
ans += solver.query_X(l, r);
}
// Part B: Col 0 (excluding (0,0) if already counted)
if (l == 0) {
// If we counted row 0, we counted (0,0). So start from row 1.
// But query range for Y is [t, b].
// Intersection of [t, b] and [1, N-1].
int y_start = max(1, t);
if (y_start <= b) {
ans += solver.query_Y(y_start, b);
}
}
// Part C: Grid [1..N-1] x [1..N-1]
// Intersection of query [t, b] x [l, r] with [1, N-1] x [1, N-1]
int t_prime = max(1, t);
int l_prime = max(1, l);
if (t_prime <= b && l_prime <= r) {
// We need sum in [t_prime, b] x [l_prime, r]
// Maps to calc_grid_sum args: calc(row_idx, col_idx)
// Indices in calc are inclusive max row/col
// Global row index i maps to calc arg i.
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;
}
