// this is the second time this year mosaic has caused me pain
#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
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 N = X.size();
while(N<3) {
X.push_back(0);
Y.push_back(0);
N++;
}
int gr[N][3], gr2[3][N];
for(int i=0;i<N;i++) gr[i][0]=Y[i];
for(int i=0;i<3;i++) gr[0][i]=X[i];
for(int i=0;i<3;i++) gr2[i][0]=Y[i];
for(int i=0;i<N;i++) gr2[0][i]=X[i];
for(int i=1;i<N;i++) for(int j=1;j<3;j++) gr[i][j]=!(gr[i-1][j]||gr[i][j-1]);
for(int i=1;i<3;i++) for(int j=1;j<N;j++) gr2[i][j]=!(gr2[i-1][j]||gr2[i][j-1]);
vector<int> arr(2*N-4,0);
vector<long long> arr2(2*N-4);
auto trapezium = [&arr, &arr2](int a, int b, int c, int d) {
long long ans = arr2[b] - arr2[a-1] - (a - 1LL) * (arr[b] - arr[a-1]);
ans += (arr[c-1] - arr[b]) * (b - a + 1LL);
ans += arr2[c-1] - arr2[d] + (d + 1LL) * (arr[d] - arr[c-1]);
return ans;
// part 1: a to b
// part 2: b+1 to c-1
// part 3: c to d
// (d+1-x) (arr[x])
};
for(int i=N-1;i>2;i--) arr[N-i]=gr[i][2];
for(int i=2;i<N;i++) arr[N+i-4]=gr2[2][i];
for(int i=1;i<2*N-4;i++) {
arr2[i] = arr2[i-1] + i * arr[i];
arr[i]+=arr[i-1];
}
for(int i=0;i<3;i++) for(int j=1;j<N;j++)
gr2[i][j]+=gr2[i][j-1];
for(int i=0;i<3;i++) for(int j=1;j<N;j++)
gr[j][i]+=gr[j-1][i];
// (N-1, 2) -> 2-(N-1) = 3 - N -> + (N - 2).
// (2, N-1) -> N - 3 -> 2N - 3???
int Q = (int)T.size();
std::vector<long long> C(Q, 0);
for(int i=0;i<Q;i++) {
if(B[i] < 2) {
for(int j=T[i];j<=B[i];j++)
C[i] += gr2[j][R[i]]-(L[i]?gr2[j][L[i]-1]:0);
continue;
}
if(R[i] < 2) {
for(int j=L[i];j<=R[i];j++)
C[i] += gr[B[i]][j]-(T[i]?gr[T[i]-1][j]:0);
continue;
}
while(L[i] < 2) {
C[i] += gr[B[i]][L[i]]-(T[i]?gr[T[i]-1][L[i]]:0);
L[i]++;
}
while(T[i] < 2) {
C[i] += gr2[T[i]][R[i]]-(L[i]?gr2[T[i]][L[i]-1]:0);
T[i]++;
}
C[i] += trapezium(L[i]-B[i]+(N-2),L[i]-T[i]+(N-2),R[i]-B[i]+(N-2),R[i]-T[i]+(N-2));
// Start: L - D
// Mid: L - T
// Then: R - D
// Last: R - T
// L - D to L - T: [x - (L - D) + 1] *
}
return C;
}
