#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}, mpref, msuff;
int k = 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);
k = a.size();
mpref.resize(k+1);
msuff.resize(k+1);
for (int i = 0; i < k; i++) {
mpref[i+1] = mpref[i]+(i+1)*a[i];
msuff[i+1] = msuff[i]+(k-i)*a[i];
}
//for (ll x : a) cout << x << " "; cout << endl;
//for (ll x : pref) cout << x << " "; cout << endl;
//for (ll x : mpref) cout << x << " "; cout << endl;
//for (ll x : msuff) 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];
//cout << t << " - " << b << " " << l << " - " << r << endl;
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);
ll mn = min(b-t, r-l);
//cout << mn << endl;
ll plm = tocord(b-mn, l), prm = tocord(t, r-mn);
//cout << pl << " " << plm << " " << prm << " " << pr << endl;
ll suml = mn ? mpref[plm]-mpref[pl]-(pref[plm]-pref[pl])*pl : 0;
ll sumr = mn ? msuff[pr+1]-msuff[prm+1]-(pref[pr+1]-pref[prm+1])*(k-pr-1) : 0;
//cout << msuff[pr+1]-msuff[prm+1] << " " << (pref[pr+1]-pref[prm+1]) << " " << (k-pr-1) << endl;
ll summ = (pref[prm+1]-pref[plm])*(mn+1);
//cout << suml << " " << summ << " " << sumr << endl << endl;
sum += suml+summ+sumr;
//cout << sum << " expected " << ans[qq] << endl;
//assert(ans[qq] == sum);
ans[qq] = sum;
}
return ans;
}
