#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)
{
vector<int> x = X, y = Y, t = T, b = B, l = L, r = R;
int n = (int)x.size(), q = (int)t.size();
if(n <= 5000)
{
vector a(n, vector<int>(n));
for(int i = 0; i < n; i++)
{
a[0][i] = x[i];
a[i][0] = y[i];
}
for(int i = 1; i < n; i++)
for(int j = 1; j < n; j++)
a[i][j] = a[i - 1][j] == 0 and a[i][j - 1] == 0;
vector pref(n + 1, vector<int>(n + 1));
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
pref[i + 1][j + 1] = pref[i + 1][j] + pref[i][j + 1] - pref[i][j] + a[i][j];
}
}
vector<long long> res(q);
for(int i = 0; i < q; i++)
{
int i1 = t[i], j1 = l[i];
int i2 = b[i], j2 = r[i];
res[i] = pref[i2 + 1][j2 + 1] - pref[i1][j2 + 1] - pref[i2 + 1][j1] + pref[i1][j1];
}
return res;
}
vector<long long> res(q);
for(int i = 0; i < q; i++)
{
int i1 = t[i], i2 = b[i];
if(i1 == i2 and i1 == 0)
{
res[i] = 0;
continue;
}
i1 += i1 == 0;
i2 = max(i1, i2);
int j1 = l[i], j2 = r[i];
if(j1 == j2 and j1 == 0)
{
res[i] = 0;
continue;
}
j1 += j1 == 0;
j2 = max(j1, j2);
int dis1 = i2 - i1 + 1;
int dis2 = j2 - j1 + 1;
long long curr = dis1 * 1ll * dis2 / 2;
if(dis1 % 2 == dis2 % 2 and dis1 % 2 == 1)
{
curr += i1 % 2 == j1 % 2;
}
res[i] = curr;
}
return res;
}
