#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; }