#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 = X.size();
int Q = T.size();
vector<long long> C(Q, X[0]);
if (N == 1) {
return C;
}
vector<vector<long long>> sums(N+1, vector<long long>(N+1, 0));
for (int i = 1; i <= N; i++) {
sums[1][i] = sums[1][i-1] + X[i-1];
sums[i][1] = sums[i-1][1] + Y[i-1];
}
vector<int> x(N-1), y(N-1);
x[0] = y[0] = not(X[1] or Y[1]);
for (int i = 1; i < N-1; i++) {
x[i] = not(x[i-1] or X[i+1]);
y[i] = not(y[i-1] or Y[i+1]);
}
for (int i = 2; i <= N; i++) {
for (int j = 2; j <= N; j++) {
sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + (i <= j ? x[j-i] : y[i-j]);
}
}
for (int i = 0; i < Q; i++) {
C[i] = sums[B[i]+1][R[i]+1] - sums[T[i]][R[i]+1] - sums[B[i]+1][L[i]] + sums[T[i]][L[i]];
}
return C;
}
