#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];
}
}
vi arr(2*N-5);
int offset = (N-1)-2;
for (int i = N-1; i >= 2; i--) arr[2-i+offset] = mat[2][i];
for (int i = 2; i < N; i++) arr[i-2+offset] = mat[i][2];
// for (auto x : arr) cout << x << " ";
// cout << endl;
vi sumArr(2*N-5), incrArr(2*N-5), decrArr(2*N-5);
for (int i = 0; i < arr.size(); i++) {
sumArr[i] = (i > 0? sumArr[i-1] : 0) + arr[i];
incrArr[i] = (i > 0? incrArr[i-1] : 0) + i*arr[i];
decrArr[i] = (i > 0? decrArr[i-1] : 0) + (2*N-5-i-1)*arr[i];
}
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];
// }
// }
int incrR = T[i]-R[i]+offset;
int incrL = min(B[i]-R[i]+offset, T[i]-L[i]+offset)-1;
int decrR = max(B[i]-R[i]+offset, T[i]-L[i]+offset)+1;
int decrL = B[i]-L[i]+offset;
C[i] += min(B[i]-T[i]+1, R[i]-L[i]+1)*(sumArr[decrR-1]-sumArr[incrL]);
C[i] += (incrArr[incrL]-(incrR > 0 ? incrArr[incrR-1] : 0))+(1-incrR)*(sumArr[incrL]-(incrR > 0 ? sumArr[incrR-1] : 0));
C[i] += (decrArr[decrL]-(decrR > 0 ? decrArr[decrR-1] : 0))+(1-(2*N-5-decrL-1))*(sumArr[decrL]-(decrR > 0 ? sumArr[decrR-1] : 0));
// cout << decrR << " " << decrL << endl;
// cout << (decrArr[decrL]-(decrR > 0 ? decrArr[decrR-1] : 0))+(1-(2*N-5-decrL-1))*(sumArr[decrL]-(decrR > 0 ? sumArr[decrR-1] : 0)) << endl;
}
return C;
}
