#include <vector>
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();
// 第 1 行与第 1 列
vector<int> M1(N, 0);
vector<int> Mcol1(N, 0);
if (N > 1) {
M1[0] = Y[1];
for (int j = 1; j < N; ++j) {
M1[j] = 1 - (X[j] | M1[j-1]);
}
Mcol1[0] = X[1];
for (int i = 1; i < N; ++i) {
Mcol1[i] = 1 - (Mcol1[i-1] | Y[i]);
}
}
// P_0 是对角线值 V 的前缀和，P_1 是 k * V 的前缀和
// 平移 N 使得索引均为非负数
vector<long long> P_0(2 * N + 2, 0);
vector<long long> P_1(2 * N + 2, 0);
if (N > 1) {
for (int k = 2 - N; k <= N - 2; ++k) {
long long v = 0;
if (k >= 0) {
v = M1[k + 1];
} else {
v = Mcol1[1 - k];
}
int idx = k + N;
P_0[idx] = P_0[idx - 1] + v;
P_1[idx] = P_1[idx - 1] + (long long)k * v;
}
}
vector<long long> P_X(N, 0);
vector<long long> P_Y(N, 0);
P_X[0] = X[0];
for (int i = 1; i < N; ++i) P_X[i] = P_X[i-1] + X[i];
P_Y[0] = Y[0];
for (int i = 1; i < N; ++i) P_Y[i] = P_Y[i-1] + Y[i];
// 助手函数：获取 V 范围内的前缀和
auto sum_V = [&](long long k1, long long k2) -> long long {
if (k1 > k2) return 0;
int idx2 = k2 + N;
int idx1 = k1 - 1 + N;
return P_0[idx2] - P_0[idx1];
};
auto sum_kV = [&](long long k1, long long k2) -> long long {
if (k1 > k2) return 0;
int idx2 = k2 + N;
int idx1 = k1 - 1 + N;
return P_1[idx2] - P_1[idx1];
};
// 获取内部矩形 [1, i] x [1, j] 的 1 的总数
auto get_S = [&](long long i, long long j) -> long long {
if (i <= 0 || j <= 0) return 0;
long long ans = 0;
if (i <= j) {
if (1 - i <= -1) {
ans += i * sum_V(1 - i, -1) + sum_kV(1 - i, -1);
}
if (0 <= j - i) {
ans += i * sum_V(0, j - i);
}
if (j - i + 1 <= j - 1) {
ans += j * sum_V(j - i + 1, j - 1) - sum_kV(j - i + 1, j - 1);
}
} else {
if (1 - i <= j - i) {
ans += i * sum_V(1 - i, j - i) + sum_kV(1 - i, j - i);
}
if (j - i + 1 <= -1) {
ans += j * sum_V(j - i + 1, -1);
}
if (0 <= j - 1) {
ans += j * sum_V(0, j - 1) - sum_kV(0, j - 1);
}
}
return ans;
};
// 整体从左上角 [0, 0] 到 [i, j] 的前缀和
auto get_F = [&](long long i, long long j) -> long long {
if (i < 0 || j < 0) return 0;
return get_S(i, j) + P_X[j] + P_Y[i] - X[0];
};
// 处理所有的问题反馈给 Salma 的好奇朋友 Yasmin
vector<long long> C(Q);
for (int q = 0; q < Q; ++q) {
long long t = T[q], b = B[q], l = L[q], r = R[q];
C[q] = get_F(b, r) - get_F(t - 1, r) - get_F(b, l - 1) + get_F(t - 1, l - 1);
}
return C;
}
