#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <vector>
using int64 = long long;
std::vector<int64> 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) {
const int n = X.size();
std::vector mp_x(6, std::vector<bool>(n + 6));
std::vector mp_y(n + 6, std::vector<bool>(6));
auto set = [&](int x, int y, int v) {
if (x <= 5) {
mp_x[x][y] = v;
}
if (y <= 5) {
mp_y[x][y] = v;
}
};
auto get = [&](int x, int y) {
if (x <= 5) {
return mp_x[x][y];
}
return mp_y[x][y];
};
for (int i = 0; i < n; ++i) {
set(0, i, X[i]);
set(i, 0, Y[i]);
}
int min = 0, max = 0;
for (int i = 1; i <= 5; ++i) {
for (int j = 1; j < n; ++j) {
set(i, j, !get(i - 1, j) && !get(i, j - 1));
int v = i - j;
min = std::min(min, i - j);
max = std::max(max, i - j);
}
}
for (int j = 1; j <= 5; ++j) {
for (int i = 1; i < n; ++i) {
set(i, j, !get(i - 1, j) && !get(i, j - 1));
int v = i - j;
min = std::min(min, i - j);
max = std::max(max, i - j);
}
}
std::vector<int> marked(max - min + 1);
for (int i = 1; i <= 5; ++i) {
for (int j = 1; j < n; ++j) {
if (!get(i, j)) {
continue;
}
int v = i - j;
marked[v - min] = true;
}
}
for (int j = 1; j <= 5; ++j) {
for (int i = 1; i < n; ++i) {
if (!get(i, j)) {
continue;
}
int v = i - j;
marked[v - min] = true;
}
}
auto get_pt = [&](int x, int y) -> int {
if (x <= 5 or y <= 5) {
return get(x, y);
}
return marked[(x - y) - min];
};
std::vector prefxs(6, std::vector<int>(n));
std::vector prefys(6, std::vector<int>(n));
for (int i = 0; i <= 5; ++i) {
for (int j = 0; j < n; ++j) {
prefxs[i][j] = get_pt(i, j);
prefys[i][j] = get_pt(j, i);
}
std::partial_sum(prefxs[i].begin(), prefxs[i].end(), prefxs[i].begin());
std::partial_sum(prefys[i].begin(), prefys[i].end(), prefys[i].begin());
}
auto prefx = [&](int x, int y1, int y2) {
return prefxs[x][y2] - (y1 == 0 ? 0 : prefxs[x][y1 - 1]);
};
auto prefy = [&](int y, int x1, int x2) {
return prefys[y][x2] - (x1 == 0 ? 0 : prefys[y][x1 - 1]);
};
struct adv {
std::vector<int> marked;
std::vector<int64> pref, prefa;
int n;
adv(std::vector<int> marked) : n(marked.size()), marked(marked), pref(marked.size()), prefa(marked.size()) {
for (int64 i = 0; i < marked.size(); ++i) {
prefa[i] = (i + 1) * marked[i];
}
std::partial_sum(prefa.begin(), prefa.end(), prefa.begin());
std::partial_sum(marked.begin(), marked.end(), pref.begin());
}
int64 querys(int l, int len) {
int r = l + len - 1;
return pref[r] - pref[l - 1];
}
int64 query(int l, int len) {
int r = l + len - 1;
return prefa[r] - prefa[l - 1] - l * (pref[r] - pref[l - 1]);
}
int64 queryf(int l, int len) {
return query(n - l - 1, len);
}
};
adv adv_left(marked);
std::reverse(marked.begin(), marked.end());
adv adv_right(marked);
std::reverse(marked.begin(), marked.end());
std::vector<int64> ans;
for (int i = 0; i < T.size(); ++i) {
int x1 = T[i], y1 = L[i], x2 = B[i], y2 = R[i];
int64 cur = 0;
while (x1 <= x2 and x1 <= 5) {
cur += prefx(x1, y1, y2);
x1++;
}
if (x1 > x2) {
ans.push_back(cur);
continue;
}
while (y1 <= y2 and y1 <= 5) {
cur += prefy(y1, x1, x2);
y1++;
}
if (y1 > y2) {
ans.push_back(cur);
continue;
}
int steps = x2 - x1 + 1;
int len = y2 - y1 + 1;
int beg = x1 - y2 - min;
int reached = std::min(steps, len);
int mid_cnt = std::abs(steps - len) + 1;
int part_len = (len + steps - 1 - mid_cnt) / 2;
int64 p1 = adv_left.query(beg, part_len);
int64 p2 = reached * adv_left.querys(beg + part_len, mid_cnt);
int64 p3 = adv_right.queryf(beg + 2 * part_len + mid_cnt - 1, part_len);
ans.push_back(cur + p1 + p2 + p3);
}
return ans;
}
