#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)); vector<vector<bool>> full(N, vector<bool>(N)); for (int i = 1; i <= N; i++) { full[0][i-1] = X[i-1]; full[i-1][0] = Y[i-1]; sums[1][i] = sums[1][i-1] + X[i-1]; sums[i][1] = sums[i-1][1] + Y[i-1]; } for (int i = 1; i < N; i++) { for (int j = 1; j < N; j++) { full[i][j] = not(full[i-1][j] or full[i][j-1]); } } for (int i = 2; i <= N; i++) { for (int j = 2; j <= N; j++) { full[i-1][j-1] = not(full[i-2][j-1] or full[i-1][j-2]); sums[i][j] = sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1] + full[i-1][j-1]; } } 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; }