#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
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(), q = B.size();
vector <long long> anss;
int row[3][n], col[3][n];
for (int i = 0; i < n; i++){
row[0][i] = X[i];
col[0][i] = Y[i];
}
for (int i = 1; i < 3; i++){
bool top = Y[i];
row[i][0] = Y[i];
for (int j = 1; j < n; j++){
if (!row[i-1][j] && !top) row[i][j] = 1;
else row[i][j] = 0;
top = row[i][j];
}
}
for (int i = 1; i < 3; i++){
bool top = X[i];
col[i][0] = X[i];
for (int j = 1; j < n; j++){
if (!col[i-1][j] && !top) col[i][j] = 1;
else col[i][j] = 0;
top = col[i][j];
}
}
vector <int> ones;
for (int i = 2; i < n; i++){
if (row[2][i]){
ones.push_back(2 - i);
}
if (col[2][i] && i != 2){
ones.push_back(i - 2);
}
}
sort(ones.begin(), ones.end());
int worthr[3][n], worthc[3][n];
for (int i = 0; i < 3; i++){
for (int j = 0; j < n; j++){
if (j == 0){
worthr[i][j] = row[i][j];
worthc[i][j] = col[i][j];
}
else{
worthr[i][j] = worthr[i][j-1] + row[i][j];
worthc[i][j] = worthc[i][j-1] + col[i][j];
}
}
}
for (int i = 0; i < q; i++){
long long ans = 0;
int t = T[i], b = B[i], l = L[i], r = R[i];
if (b > 2 && l <= 2){
int r1 = min(2, r);
int t1 = max(3, t);
for (int j = l; j <= r1; j++){
ans += worthc[j][b] - worthc[j][t1-1];
}
}
if (r > 2 && t <= 2){
int b1 = min(2, b);
int l1 = max(3, l);
for (int j = t; j <= b1; j++){
ans += worthr[j][r] - worthr[j][l1-1];
}
}
if (l <= 2 && t <= 2){
int r1 = min(2, r);
int b1 = min(2, r);
for (int j = l; j <= r1; j++){
if (t != 0) ans += worthc[j][b1] - worthc[j][t - 1];
else ans += worthc[j][b1];
}
}
l = max(l, 3);
t = max(t, 3);
int h1 = b - t + 1, l1 = r - l + 1;
for (auto u : ones){
if (b - l > u) break;
if (t - r < u) continue;
int y = t - u;
if (y >= l) ans += min(h1, r - y + 1);
else{
ans += min(l1, h1 - l + y);
}
}
anss.push_back(ans);
}
return anss;
}
