#include "mosaic.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
void maxs(int &x, int y) {
x = max(x, y);
}
vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T,
vector<int> B, vector<int> L, vector<int> R) {
int n = X.size();
vector a(n, vector(min(n, 3), false));
vector pref(max(5, n + 1), vector(5, 0));
a[0] = vector(n, false);
for (int i = 0; i < n; i++) {
a[0][i] = X[i]; a[i][0] = Y[i];
}
for (int i = 1; i < n; i++) {
if (i <= 2) a[i].resize(n);
for (int j = 1; j < a[i].size(); j++) {
a[i][j] = !(a[i - 1][j] | a[i][j - 1]);
}
}
for (int i = 0; i <= 3; i++) pref[i].assign(n + 1, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < a[i].size(); j++) {
pref[i + 1][j + 1] = a[i][j] + pref[i][j + 1] + pref[i + 1][j] - pref[i][j];
}
}
auto get = [&](int x, int y) -> int {
assert(min(x, y) >= 2);
int d = min(x, y) - 2;
x -= d, y -= d;
if (y == 2) {
return n - 1 - x;
}
return n - 3 + (y - 2);
};
auto sum = [&](int x1, int y1, int x2, int y2) -> int {
// assert(max(x2, y2) <= 2);
x1++, x2++, y1++, y2++;
// cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << pref[x2][y2] << endl;
return pref[x2][y2] - pref[x1 - 1][y2] - pref[x2][y1 - 1] + pref[x1 - 1][y1 - 1];
};
vector<int> pref2(n * 3);
vector<ll> pref3(n * 3);
if (n >= 3) {
int z = 0;
for (int i = n - 1; i >= 2; i--) {
pref2[z] = a[i][2];
if (z > 0) pref2[z] += pref2[z - 1];
z++;
}
for (int i = 3; i < n; i++) {
pref2[z] = pref2[z - 1];
pref2[z] += a[2][i];
z++;
}
for (int i = 0; i < n * 3; i++) {
pref3[i] = pref2[i] + (i > 0 ? pref3[i - 1] : 0);
}
}
vector<ll> ans(T.size());
for (int i = 0; i < T.size(); i++) {
ll now = 0;
for (int x = T[i]; x <= min(1, B[i]); x++) {
auto [y1, y2] = make_pair(L[i], R[i]);
y1++, y2++;
now += pref[x+1][y2] - pref[x+1][y1 - 1] - pref[x][y2] + pref[x][y1 - 1];
}
auto [x1, x2] = make_pair(T[i], B[i]);
auto [y1, y2] = make_pair(L[i], R[i]);
// some small shits
maxs(x1, 2);
if (x1 > x2) {
ans[i] = now;
continue;
}
if (y1 < 2) {
now += sum(x1, y1, x2, min(1, y2));
y1 = 2;
}
if (y1 > y2) {
ans[i] = now;
continue;
}
auto [l, r] = make_pair(get(x2, y2), get(x1, y2));
// cout << l << ' ' << r << endl;
ll sum = pref3[r] - (l > 0 ? pref3[l - 1] : 0);
now += sum;
l = get(x2, y1) - 1, r = get(x1, y1) - 1;
maxs(l, 0);
if (l <= r) {
sum = pref3[r] - (l > 0 ? pref3[l - 1] : 0);
now -= sum;
}
ans[i] = now;
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < a[i].size(); j++) cout << a[i][j] << ' ';
// cout << endl;
// }
return ans;
}
