#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long> mosaic(
vector<int> X, vector<int> Y,
vector<int> T, vector<int> B,
vector<int> L, vector<int> R
) {
int n = size(X);
vector<vector<int>> a(n);
a[0] = X;
for (int i = 1; i < n; i++)
{
int len = i < 3 ? n : 3;
a[i].resize(len);
a[i][0] = Y[i];
for (int j = 1; j < len; j++)
a[i][j] = (a[i - 1][j] | a[i][j - 1]) ^ 1;
}
vector<vector<long long>> s(n);
for (int i = 0; i < n; i++)
{
int len = i < 3 ? n : 3;
s[i].resize(len);
s[i][0] = a[i][0];
if (i)
s[i][0] += s[i - 1][0];
for (int j = 1; j < len; j++)
{
s[i][j] = s[i][j - 1] + a[i][j];
if (i)
s[i][j] += s[i - 1][j] - s[i - 1][j - 1];
}
}
vector<long long> sumRow(n), sumCol(n), cntRow(n), cntCol(n);
for (int i = 2; i < n; i++)
{
sumRow[i] = sumRow[i - 1] + (a[2][i] ? i : 0);
cntRow[i] = cntRow[i - 1] + a[2][i];
sumCol[i] = sumCol[i - 1] + (a[i][2] ? i : 0);
cntCol[i] = cntCol[i - 1] + a[i][2];
}
auto getColTriangle = [&](int x, int xx)
{
return 1LL * xx * (cntCol[xx - 1] - cntCol[x - 2]) - (sumCol[xx - 1] - sumCol[x - 2]);
};
auto getRowTriangle = [&](int y, int yy)
{
return 1LL * yy * (cntRow[yy - 1] - cntRow[y - 2]) - (sumRow[yy - 1] - sumRow[y - 2]);
};
auto get = [&](int x, int y)
{
if (x < 0 || y < 0)
return 0LL;
if (x < 3 || y < 3)
return s[x][y];
long long res = s[2][y] + s[x][2] - s[2][2];
if (x <= y)
{
if (x >= 4)
res += getColTriangle(4, x);
res += getRowTriangle(y - (x - 3), y);
res += (cntRow[y - (x - 1)] - cntRow[1]) * (x - 2);
}
else
{
if (y >= 4)
res += getRowTriangle(4, y);
res += getColTriangle(x - (y - 3), x);
res += (cntCol[x - (y - 1)] - cntCol[1]) * (y - 2);
}
return res;
};
int q = size(T);
vector<long long> ans(q);
for (int i = 0; i < q; i++)
{
ans[i] = get(B[i], R[i]) + get(T[i] - 1, L[i] - 1);
ans[i] -= get(B[i], L[i] - 1) + get(T[i] - 1, R[i]);
}
return ans;
}
