#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 = (int)X.size(); int Q = (int)T.size(); vector<int> row1(N, 0), col1(N, 0), row2(N, 0), col2(N, 0); // Build row 1 and column 1 if (N >= 2) { row1[0] = Y[1]; for (int j = 1; j < N; ++j) { row1[j] = (X[j] == 0 && row1[j - 1] == 0) ? 1 : 0; } col1[0] = X[1]; for (int i = 1; i < N; ++i) { col1[i] = (col1[i - 1] == 0 && Y[i] == 0) ? 1 : 0; } } // Build row 2 and column 2 if (N >= 3) { row2[0] = Y[2]; row2[1] = (row1[1] == 0 && row2[0] == 0) ? 1 : 0; for (int j = 2; j < N; ++j) { row2[j] = (row1[j] == 0 && row2[j - 1] == 0) ? 1 : 0; } col2[0] = X[2]; col2[1] = (col2[0] == 0 && col1[1] == 0) ? 1 : 0; for (int i = 2; i < N; ++i) { col2[i] = (col2[i - 1] == 0 && col1[i] == 0) ? 1 : 0; } } // Prefix sums on row 0, row 1 vector<long long> prefRow0(N, 0), prefRow1(N, 0); if (N > 0) { long long s = 0; for (int j = 0; j < N; ++j) { s += X[j]; prefRow0[j] = s; } s = 0; for (int j = 0; j < N; ++j) { s += row1[j]; prefRow1[j] = s; } } // Prefix sums on col 0, col 1 vector<long long> prefCol0(N, 0), prefCol1(N, 0); if (N > 0) { long long s = 0; for (int i = 0; i < N; ++i) { s += Y[i]; prefCol0[i] = s; } s = 0; for (int i = 0; i < N; ++i) { s += col1[i]; prefCol1[i] = s; } } // Z[d] for d in [-(N-3), ..., (N-3)] int M = N - 3; // if M < 0, no inner (i>=2,j>=2) core exists vector<long long> ps0, ps1; // prefix of Z, prefix of d*Z if (M >= 0) { int len = 2 * M + 1; ps0.assign(len + 1, 0); ps1.assign(len + 1, 0); for (int idx = 0; idx < len; ++idx) { int d = idx - M; int val = (d >= 0) ? row2[2 + d] : col2[2 - d]; ps0[idx + 1] = ps0[idx] + val; ps1[idx + 1] = ps1[idx] + 1LL * val * d; } } auto sumRangePS = [&](const vector<long long>& ps, int lo, int hi) -> long long { if (M < 0 || lo > hi) return 0; lo = max(lo, -M); hi = min(hi, M); if (lo > hi) return 0; int Lidx = lo + M; int Ridx = hi + M; return ps[Ridx + 1] - ps[Lidx]; }; auto sumLinear = [&](int lo, int hi, long long a, long long b) -> long long { // sum_{d=lo..hi} Z[d] * (a*d + b) if (lo > hi) return 0; long long S0 = sumRangePS(ps0, lo, hi); long long S1 = sumRangePS(ps1, lo, hi); return a * S1 + b * S0; }; auto coreSum = [&](int t, int b, int l, int r) -> long long { // sum on rectangle [t..b] x [l..r], assuming t>=2 and l>=2 if (M < 0 || t > b || l > r) return 0; long long h = b - t + 1; long long w = r - l + 1; int d0 = l - b; int d1 = l - t; int d2 = r - b; int d3 = r - t; int x = min(d1, d2); int y = max(d1, d2); long long m = min(h, w); long long ans = 0; // Increasing part: cnt(d) = d - d0 + 1 ans += sumLinear(d0, x, 1, 1LL - d0); // Plateau: cnt(d) = m ans += sumLinear(x + 1, y, 0, m); // Decreasing part: cnt(d) = d3 - d + 1 ans += sumLinear(y + 1, d3, -1, 1LL * d3 + 1); return ans; }; auto rowRange = [&](const vector<long long>& pref, int l, int r) -> long long { if (l > r) return 0; long long res = pref[r]; if (l > 0) res -= pref[l - 1]; return res; }; auto colRange = [&](const vector<long long>& pref, int t, int b) -> long long { if (t > b) return 0; long long res = pref[b]; if (t > 0) res -= pref[t - 1]; return res; }; vector<long long> C(Q, 0); for (int k = 0; k < Q; ++k) { int t = T[k], b = B[k], l = L[k], r = R[k]; long long ans = 0; // Part 1: rows 0 and 1 int rb = min(b, 1); for (int i = t; i <= rb; ++i) { if (i == 0) ans += rowRange(prefRow0, l, r); else ans += rowRange(prefRow1, l, r); } // Parts with rows >= 2 int t2 = max(t, 2); if (t2 <= b) { // Part 2: columns 0 and 1 int cmax = min(r, 1); for (int j = l; j <= cmax; ++j) { if (j == 0) ans += colRange(prefCol0, t2, b); else ans += colRange(prefCol1, t2, b); } // Part 3: inner core i>=2, j>=2 int l2 = max(l, 2); if (l2 <= r) { ans += coreSum(t2, b, l2, r); } } C[k] = ans; } return C; }