#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> L, std::vector<int> R) {
int n = X.size();
int m = min(n, 3);
vvl gr(m+1, vl(n+1)), gc(n+1, vl(m+1));
for (int i = 0; i < n; i++) {
gr[1][i+1] = X[i], gc[i+1][1] = Y[i];
if (i < m) gr[i+1][1] = Y[i], gc[1][i+1] = X[i];
}
for (int i = 2; i <= m; i++) {
for (int j = 2; j <= n; j++) {
gr[i][j] = !gr[i-1][j]&&!gr[i][j-1];
gc[j][i] = !gc[j-1][i]&&!gc[j][i-1];
}
}
vl a, pref{0};
if (n >= 3) {
for (int i = n; i >= 3; i--) a.push_back(gc[i][3]);
for (int i = 4; i <= n; i++) a.push_back(gr[3][i]);
for (auto x : a) pref.push_back(pref.back()+x);
}
//for (ll x : a) cout << x << " "; cout << endl;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
gr[i][j] += gr[i-1][j]+gr[i][j-1]-gr[i-1][j-1];
gc[j][i] += gc[j-1][i]+gc[j][i-1]-gc[j-1][i-1];
}
}
//for (auto &r : gr) {
// for (auto x : r) cout << x << " ";
// cout << endl;
//}
//cout << endl;
//for (auto &r : gc) {
// for (auto x : r) cout << x << " ";
// cout << endl;
//}
auto tocord = [&](int i, int j) -> int {
if (i > j) i -= j, j = 0;
else j -= i, i = 0;
if (j == 0) return n-i-3;
else return n-3+j;
};
int q = (int)T.size();
vl ans(q);
//for (int i = 3; i < n; i++) {
// for (int j = 3; j < n; j++) cout << "("<<i<<","<<j<<")" << tocord(i, j) << " ";
// cout << endl;
//}
for (int qq = 0; qq < q; qq++) {
ll t = T[qq], b = B[qq], l = L[qq], r = R[qq];
ll sum = 0;
if (t < 3) {
ll bb = min(b, 2ll)+1;
sum += gr[bb][r+1]-gr[t][r+1]-gr[bb][l]+gr[t][l];
t = 3;
if (b < 3) {
ans[qq] = sum;
continue;
}
}
if (l < 3) {
ll rr = min(r, 2ll)+1;
sum += gc[b+1][rr]-gc[t][rr]-gc[b+1][l]+gc[t][l];
l = 3;
if (r < 3) {
ans[qq] = sum;
continue;
}
}
ll pl = tocord(b, l), pr = tocord(t, r);
sum += pref[pr+1]-pref[pl];
ans[qq] = sum;
}
return ans;
}
