#include <bits/stdc++.h>
#include "mosaic.h"
using namespace std;
typedef long long ll;
ll n, q;
vector<vector<ll>> lay, layPref;
vector<ll> stairs;
vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
n = X.size();
q = T.size();
lay = vector<vector<ll>>(5, vector<ll>(2*n-1));
layPref = vector<vector<ll>>(5, vector<ll>(2*n));
stairs = vector<ll>(2*n);
vector<ll> res(q);
for (int i = 0; i < n; i++) {
lay[0][n-1+i] = X[i];
lay[0][n-1-i] = Y[i];
}
for (int L = 1; L < min(5ll, n); L++) {
ll mid = n-1-L;
lay[L][mid] = !lay[L-1][mid] && !lay[L-1][mid+2];
for (int i = mid+1; i < 2*n-1-2*L; i++) {
lay[L][i] = !lay[L][i-1] && !lay[L-1][i+2];
}
for (int i = mid-1; i >= 0; i--) {
lay[L][i] = !lay[L][i+1] && !lay[L-1][i];
}
}
for (int L = 0; L < min(5ll, n); L++) {
for (int i = 0; i < 2*n-1-2*L; i++) {
layPref[L][i+1] = layPref[L][i] + lay[L][i];
}
}
if (n >= 5) {
for (int i = 0; i < 2*n-1; i++) {
stairs[i+1] = stairs[i] + (i+1)*lay[4][i];
}
}
// Solve
for (int k = 0; k < q; k++) {
ll t = T[k], b = B[k], l = L[k], r = R[k];
ll ans = 0;
bool skip = false;
while (t < 5 || l < 5) {
if (t < l) { // Move t
ll L = t;
ll mid = n-1-L;
ll ref = mid-L;
ll idL = ref + l;
ll idR = ref + r;
ans += layPref[L][idR+1] - layPref[L][idL];
t++;
}
else { // Move l
ll L = l;
ll idL = n-1-b;
ll idR = n-1-t;
ans += layPref[L][idR+1] - layPref[L][idL];
l++;
}
// Check if done
if (b-t < 0 || r-l < 0) {
skip = true;
break;
}
}
if (skip) {
res[k] = ans;
continue;
}
// Get remaining area
ll idBL = n-1-b + l-4;
ll idBR = n-1-b + r-4;
ll idTL = n-1-t + l-4;
ll idTR = n-1-t + r-4;
ll idL = min(idTL, idBR);
ll idR = max(idTL, idBR);
ll idLL = idBL;
ll idRR = idTR;
ll w = min(b-t+1, r-l+1);
ans += (layPref[4][idR+1] - layPref[4][idL]) * w; // middle
ans += stairs[idL] - stairs[idLL] - (layPref[4][idL] - layPref[4][idLL])*idLL; // left
ll rightStair = stairs[idRR+1] - stairs[idR+1] - (layPref[4][idRR+1] - layPref[4][idR+1])*(idR+1);
ans += (layPref[4][idRR+1] - layPref[4][idR+1])*(idRR-idR+1) - rightStair; // right
res[k] = ans;
}
return res;
}
#ifdef TEST
#include "grader.cpp"
#endif
