#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define nL '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y,
std::vector<int> T, std::vector<int> B,
std::vector<int> L, std::vector<int> R) {
int Q = (int)T.size();
std::vector<long long> C(Q, 0);
int N = (int)X.size();
if (N <= 3) {
vvi mat(N, vi(N));
mat[0] = X;
for (int i = 0; i < N; i++) mat[i][0] = Y[i];
for (int i = 1; i < N; i++) {
for (int j = 1; j < N; j++) {
mat[i][j] = mat[i-1][j] == 0 && mat[i][j-1] == 0;
}
}
for (int i = 0; i < Q; i++) {
for (int j = T[i]; j <= B[i]; j++) {
for (int k = L[i]; k <= R[i]; k++) {
C[i] += mat[j][k];
}
}
}
return C;
}
// vvi mat(N, vi(N));
// mat[0] = X;
// for (int i = 0; i < N; i++) mat[i][0] = Y[i];
// for (int i = 1; i < N; i++) {
// for (int j = 1; j < N; j++) {
// if (j >= 3 && i > 2) break;
// mat[i][j] = mat[i-1][j] == 0 && mat[i][j-1] == 0;
// }
// }
// for (int i = 3; i < N; i++) {
// for (int j = 3; j < N; j++) {
// int d = min(i-3+1, j-3+1);
// mat[i][j] = mat[i-d][j-d];
// }
// }
// for (int i = 0; i < Q; i++) {
// for (int j = T[i]; j <= B[i]; j++) {
// for (int k = L[i]; k <= R[i]; k++) {
// C[i] += mat[j][k];
// }
// }
// }
// return C;
// N > 3
vvi mat(N);
for (int i = 0; i < 3; i++) mat[i] = vi(N);
for (int i = 3; i < N; i++) mat[i] = vi(3);
mat[0] = X;
for (int i = 0; i < N; i++) mat[i][0] = Y[i];
for (int i = 1; i < N; i++) {
for (int j = 1; j < mat[i].size(); j++) {
mat[i][j] = mat[i-1][j] == 0 && mat[i][j-1] == 0;
}
}
vvi sumCol(3, vi(N)), sumRow(3, vi(N));
for (int i = 0; i < 3; i++) {
for (int j = 0; j < N; j++) {
sumCol[i][j] = (j > 0? sumCol[i][j-1] : 0) + mat[j][i];
}
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < N; j++) {
sumRow[i][j] = (j > 0? sumRow[i][j-1] : 0) + mat[i][j];
}
}
for (int i = 0; i < Q; i++) {
while (L[i] <= R[i] && L[i] < 3) {
C[i] += sumCol[L[i]][B[i]]-(T[i] > 0? sumCol[L[i]][T[i]-1] : 0);
L[i]++;
}
if (L[i] > R[i]) continue;
while (T[i] <= B[i] && T[i] < 3) {
C[i] += sumRow[T[i]][R[i]]-(L[i] > 0? sumRow[T[i]][L[i]-1] : 0);
T[i]++;
}
if (T[i] > B[i]) continue;
for (int j = T[i]; j <= B[i]; j++) {
for (int k = L[i]; k <= R[i]; k++) {
int d = min(j-3+1, k-3+1);
C[i] += mat[j-d][k-d];
}
}
}
return C;
}
