#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];
}
}
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;
//}
int q = (int)T.size();
vl ans(q);
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;
}
}
ans[qq] = sum;
}
return ans;
}
