#include <vector>
#include <algorithm>
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 = X.size();
int Q = T.size();
// 储存前 3 行和前 3 列的数组
vector<vector<int>> M_top;
vector<vector<int>> M_left;
M_top.push_back(X);
M_left.push_back(Y);
if (N > 1) {
vector<int> row1(N), col1(N);
row1[0] = Y[1];
col1[0] = X[1];
for (int j = 1; j < N; ++j) {
row1[j] = 1 - (M_top[0][j] | row1[j-1]);
}
for (int i = 1; i < N; ++i) {
col1[i] = 1 - (col1[i-1] | M_left[0][i]);
}
M_top.push_back(row1);
M_left.push_back(col1);
}
if (N > 2) {
vector<int> row2(N), col2(N);
row2[0] = Y[2];
col2[0] = X[2];
for (int j = 1; j < N; ++j) {
row2[j] = 1 - (M_top[1][j] | row2[j-1]);
}
for (int i = 1; i < N; ++i) {
col2[i] = 1 - (col2[i-1] | M_left[1][i]);
}
M_top.push_back(row2);
M_left.push_back(col2);
}
// V[k] 储存第 2 行/列起，斜对角线 y - x = k 上的常数值
vector<long long> V(2 * N + 1, 0);
if (N > 2) {
for (int k = -(N - 3); k <= N - 3; ++k) {
if (k >= 0) {
V[k + N] = M_top[2][k + 2];
} else {
V[k + N] = M_left[2][-k + 2];
}
}
}
// 针对 V 和 k * V 的前缀和数组（移位防止负数索引）
vector<long long> P0(2 * N + 2, 0);
vector<long long> P1(2 * N + 2, 0);
for (int i = 0; i <= 2 * N; ++i) {
P0[i + 1] = P0[i] + V[i];
P1[i + 1] = P1[i] + (long long)(i - N) * V[i];
}
auto get_sum_V = [&](long long k1, long long k2) -> long long {
if (k1 > k2) return 0;
return P0[k2 + N + 1] - P0[k1 + N];
};
auto get_sum_kV = [&](long long k1, long long k2) -> long long {
if (k1 > k2) return 0;
return P1[k2 + N + 1] - P1[k1 + N];
};
// 一维边界数组的前缀和
vector<int> sum_X(N + 1, 0), sum_Y(N + 1, 0);
for (int i = 0; i < N; ++i) {
sum_X[i+1] = sum_X[i] + X[i];
sum_Y[i+1] = sum_Y[i] + Y[i];
}
vector<int> sum_M_top1(N + 1, 0), sum_M_left1(N + 1, 0);
if (N > 1) {
for (int i = 0; i < N; ++i) {
sum_M_top1[i+1] = sum_M_top1[i] + M_top[1][i];
sum_M_left1[i+1] = sum_M_left1[i] + M_left[1][i];
}
}
// 求从左上角 [0, 0] 到 [i, j] 组成的子矩阵内黑瓷砖的总数
auto F = [&](int i, int j) -> long long {
if (i < 0 || j < 0) return 0;
long long ans = 0;
// 周边边界部分的求和
ans += sum_X[j + 1];
if (i > 0) ans += sum_Y[i + 1] - sum_Y[1];
if (i >= 1 && j >= 1) {
ans += sum_M_top1[j + 1] - sum_M_top1[1];
if (i >= 2) ans += sum_M_left1[i + 1] - sum_M_left1[2];
}
// 含有规律的核心区域 M[2...i][2...j]
if (i >= 2 && j >= 2) {
long long H = i - 1;
long long W = j - 1;
if (H <= W) {
if (-(H-1) <= -1) {
ans += H * get_sum_V(-(H-1), -1) + get_sum_kV(-(H-1), -1);
}
if (0 <= W - H) {
ans += H * get_sum_V(0, W - H);
}
if (W - H + 1 <= W - 1) {
ans += W * get_sum_V(W - H + 1, W - 1) - get_sum_kV(W - H + 1, W - 1);
}
} else {
if (-(H-1) <= -(H-W) - 1) {
ans += H * get_sum_V(-(H-1), -(H-W) - 1) + get_sum_kV(-(H-1), -(H-W) - 1);
}
if (-(H-W) <= 0) {
ans += W * get_sum_V(-(H-W), 0);
}
if (1 <= W - 1) {
ans += W * get_sum_V(1, W - 1) - get_sum_kV(1, W - 1);
}
}
}
return ans;
};
// 容斥原理 O(1) 给出单个查询的最终答案
vector<long long> C(Q);
for (int q = 0; q < Q; ++q) {
C[q] = F(B[q], R[q]) - F(T[q] - 1, R[q]) - F(B[q], L[q] - 1) + F(T[q] - 1, L[q] - 1);
}
return C;
}
