#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> a[200200], b[200200];
ll c[2][200200], d[2][200200];
int n;
ll calc(int x, int y){
if (x <= 3 || y <= 3) return b[x][y];
ll ret = b[x][3] + b[3][y] - b[3][3];
if (x <= y){
ret += d[1][x] - d[0][x] * (n+1-x);
ret += c[1][y] - c[0][y] * (n+1-y);
ret -= c[1][y-x+2] - c[0][y-x+2] * (n+1-y); // n+1 - (y-x+2) - (n+1-y) = x-2
ret += c[0][y-x+2] * (x-3);
}
else{
ret += c[1][y] - c[0][y] * (n+1-y);
ret += d[1][x] - d[0][x] * (n+1-x);
ret -= d[1][x-y+2] - d[0][x-y+2] * (n+1-x); /// n+1 - (x-y+2) - (n+1-x) = y-2
ret += d[0][x-y+2] * (y-3);
}
return ret;
}
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) {
n = X.size();
a[0].resize(n+1);
b[0].resize(n+1);
for (int i=1;i<=n;i++) a[i].resize(4);
for (int i=1;i<=3;i++) a[i].resize(n+1);
for (int j=1;j<=n;j++) a[1][j] = X[j-1];
for (int i=1;i<=n;i++) a[i][1] = Y[i-1];
for (int i=2;i<=n;i++){
for (int j=2;j<(int)a[i].size();j++){
if (!a[i][j-1] && !a[i-1][j]) a[i][j] = 1;
else a[i][j] = 0;
}
}
for (int i=1;i<=n;i++){
b[i].resize(a[i].size());
for (int j=1;j<(int)a[i].size();j++) b[i][j] = a[i][j] + b[i-1][j] + b[i][j-1] - b[i-1][j-1];
}
for (int j=3;j<=n;j++){
c[0][j] = c[0][j-1] + a[3][j];
c[1][j] = c[1][j-1] + a[3][j] * (n+1-j);
}
for (int i=4;i<=n;i++){
d[0][i] = d[0][i-1] + a[i][3];
d[1][i] = d[1][i-1] + a[i][3] * (n+1-i);
}
vector<ll> ans;
for (int i=0;i<(int)T.size();i++){
int lx = T[i] + 1, rx = B[i] + 1;
int ly = L[i] + 1, ry = R[i] + 1;
ans.push_back(calc(rx, ry) - calc(lx-1, ry) - calc(rx, ly-1) + calc(lx-1, ly-1));
}
return ans;
}
