#include "mosaic.h"
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
int n, q;
const int maxn = 2e5 + 5;
int cx[5][maxn], cy[5][maxn];
int px[5][maxn], py[5][maxn];
int d[5][5];
long long sum[maxn];
int a[maxn * 2];
long long ps[maxn * 2], pref[maxn * 2];
long long get_sum(int l, int r) {
if (l > r || r < 0) return 0;
return pref[r] - (l <= 0 ? 0 : pref[l - 1]);
}
long long get(int r, int c) {
if (r < 0 || c < 0) return 0;
long long res = get_sum(n - 5, n - 5 + c);
res -= get_sum(n - 5 - r - 1, n - 5 + c - r - 1);
// debug(r, c, res);
return res;
}
vector<long long> mosaic(vector<int> x, vector<int> y, vector<int> qt, vector<int> qb, vector<int> ql, vector<int> qr) {
q = (int)qt.size();
n = (int)x.size();
if (n < 5) {
for (int i = 0; i < n; ++i) {
d[0][i] = x[i];
d[i][0] = y[i];
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j < n; ++j) {
if (d[i - 1][j] || d[i][j - 1]) {
d[i][j] = 0;
} else {
d[i][j] = 1;
}
}
}
vector<long long> res;
for (int i = 0; i < q; ++i) {
int cnt = 0;
for (int r = qt[i]; r <= qb[i]; ++r) {
for (int c = ql[i]; c <= qr[i]; ++c) {
cnt += d[r][c];
}
}
res.push_back(cnt);
}
return res;
}
for (int i = 0; i < n; ++i) {
cx[0][i] = px[0][i] = x[i];
cy[0][i] = py[0][i] = y[i];
if (i > 0) {
px[0][i] += px[0][i - 1];
py[0][i] += py[0][i - 1];
}
}
for (int ite = 1; ite < 5; ++ite) {
cx[ite][0] = y[ite];
cy[ite][0] = x[ite];
for (int i = 1; i < n; ++i) {
if (cx[ite][i - 1] || cx[ite - 1][i]) {
cx[ite][i] = 0;
} else {
cx[ite][i] = 1;
}
if (cy[ite][i - 1] || cy[ite - 1][i]) {
cy[ite][i] = 0;
} else {
cy[ite][i] = 1;
}
}
for (int i = 0; i < n; ++i) {
px[ite][i] = cx[ite][i];
py[ite][i] = cy[ite][i];
if (i > 0) {
px[ite][i] += px[ite][i - 1];
py[ite][i] += py[ite][i - 1];
}
}
}
for (int i = n - 1; i >= 4; --i) {
a[n - i - 1] = cy[4][i];
}
for (int i = 4; i < n; ++i) {
a[n - 5 + (i - 4)] = cx[4][i];
}
// for (int i = 0; i < (n - 4) * 2 - 1; ++i) {
// cout << a[i] << " ";
// }
for (int i = 0; i < (n - 4) * 2 - 1; ++i) {
ps[i] = (i == 0 ? 0 : ps[i - 1]) + a[i];
pref[i] = (i == 0 ? 0 : pref[i - 1]) + ps[i];
}
vector<long long> res;
for (int i = 0; i < q; ++i) {
long long cur = 0;
int t = qt[i], b = qb[i], l = ql[i], r = qr[i];
while (t < 4 and t <= b) {
cur += px[t][r] - (l == 0 ? 0 : px[t][l - 1]);
++t;
}
while (l < 4 and l <= r) {
cur += py[l][b] - (t == 0 ? 0 : py[l][t - 1]);
++l;
}
if (t > b || l > r) {
res.push_back(cur);
continue;
}
l -= 4, r -= 4, t -= 4, b -= 4;
cur += get(b, r) - get(b, l - 1) - get(t - 1, r) + get(t - 1, l - 1);
res.push_back(cur);
}
return res;
}
