#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));
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]);
}
}
auto get = [&](int x, int y1, int y2) -> int {
if ((x + y1) % 2) y1++;
if ((x + y2) % 2) y2--;
if (y1 > y2) return 0;
return (y2 - y1) / 2 + 1;
};
vector<ll> ans(T.size());
for (int i = 0; i < T.size(); i++) {
auto [x1, x2] = make_pair(T[i], B[i]);
auto [y1, y2] = make_pair(L[i], R[i]);
maxs(x1, 1); maxs(y1, 1);
// cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
if (x1 > x2 or y1 > y2) continue;
int c = (x2 - x1 + 1);
int now = get(x1, y1, y2) * ((c + 1) / 2);
now += get(x1 + 1, y1, y2) * (c / 2);
// for (int x = T[i]; x <= B[i]; x++) {
// for (int y = L[i]; y <= R[i]; y++) {
// if (min(x, y) <= 2) {
// now += a[x][y];
// continue;
// }
// int d = min(x, y) - 2;
// now += a[x - d][y - d];
// }
// }
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;
// for (int i = 2; i < n - 1; i++) {
// for (int j = 2; j < n - 1; j++) {
// if (a[i][j] != a[i - 1][j - 1]) {
// cout << i << ' ' << j << endl;
// }
// // assert(a[i][j] == a[i - 1][j - 1]);
// }
// }
// return vector(T.size(), 0ll);
}
