#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define double long double
vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R){
if (X.size() <= 3){
vector<vector<int>> pre(X.size() + 1, vector<int>(X.size() + 1));
vector<vector<int>> real(X.size() + 1, vector<int>(X.size() + 1));
for (int i = 1; i <= X.size(); i++){
real[1][i] = X[i - 1];
real[i][1] = Y[i - 1];
}
for (int i = 2; i <= X.size(); i++){
for (int j = 2; j<= X.size(); j++){
real[i][j] = 1 - max(real[i - 1][j], real[i][j - 1]);
}
}
for (int i = 1; i <= X.size(); i++){
for (int j = 1; j <= X.size(); j++){
pre[i][j] = pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1] + real[i][j];
}
}
vector<long long> ans;
for (int i = 0; i < T.size(); i++){
R[i]++;
B[i]++;
ans.push_back(pre[B[i]][R[i]] - pre[T[i]][R[i]] - pre[B[i]][L[i]] + pre[T[i]][L[i]]);
}
return ans;
}
else{
vector<long long> ans;
map<int, long long> mp;
vector<int> x(X.size()), y(X.size());
x[0] = Y[1];
for (int i = 1; i < X.size(); i++){
x[i] = 1 - max(X[i], x[i - 1]);
}
y[0] = X[1];
for (int i = 1; i < Y.size(); i++){
y[i] = 1 - max(Y[i], y[i - 1]);
}
vector<int> xx(X.size()), yy(X.size());
xx[1] = y[2];
for (int i = 2; i < X.size(); i++){
xx[i] = 1 - max(x[i], xx[i - 1]);
}
yy[1] = x[2];
for (int i = 2; i < Y.size(); i++){
yy[i] = 1 - max(y[i], yy[i - 1]);
}
for (int i = 2; i < X.size(); i++){
mp[i - 2] = yy[i];
mp[-i + 2] = xx[i];
}
int sz = (int)X.size();
vector<long long> pre(2 * sz), pre1(2 * sz), pre2(2 * sz + 1);
mp[sz - 2] = x[sz - 1];
mp[sz - 1] = X[sz - 1];
mp[-sz + 2] = y[sz - 1];
mp[-sz + 1] = Y[sz - 1];
for (int i = 1; i < 2 * sz; i++){
pre[i] = pre[i - 1] + mp[i - sz];
pre1[i] = pre1[i - 1] + mp[i - sz] * i;
}
for (int i = 2 * sz - 1; i >= 1; i--){
pre2[i] = pre2[i + 1] + mp[i - sz] * (2 * sz - i);
}
vector<long long> p1x(sz + 1), p2x(sz + 1), p1y(sz + 1), p2y(sz + 1);
for (int i = 1; i <= sz; i++){
p1x[i] = p1x[i - 1] + X[i - 1];
p2x[i] = p2x[i - 1] + x[i - 1];
p1y[i] = p1y[i - 1] + Y[i - 1];
p2y[i] = p2y[i - 1] + y[i - 1];
}
for (int i = 0; i < T.size(); i++){
long long res = 0;
int t = T[i], b = B[i], l = L[i], r = R[i];
if (t == 0){
res += p1x[r + 1] - p1x[l];
t++;
}
if (t == 1){
res += p2x[r + 1] - p2x[l];
t++;
}
if (b == 0){
ans.push_back(p1x[r + 1] - p1x[l]);
continue;
}
if (b == 1){
ans.push_back(res);
continue;
}
if (l == 0){
res += p1y[b + 1] - p1y[t];
l++;
}
if (r == 0){
ans.push_back(res);
continue;
}
if (l == 1){
res += p2y[b + 1] - p2y[t];
l++;
}
if (r == 1){
ans.push_back(res);
continue;
}
int lft1 = sz + (b - l) + 1;
int ext1 = min((r - l) + 1, (b - t) + 1);
int rgt1 = lft1 - ext1;
res += pre2[rgt1] - pre2[lft1] - (pre[lft1 - 1] - pre[rgt1 - 1]) * (2 * sz - lft1);
//cout << pre[lft1] - pre[rgt1] << "\n";
int rgt2 = sz + (t - r) - 1;
int lft2 = rgt2 + ext1;
res += pre1[lft2] - pre1[rgt2] - (pre[lft2] - pre[rgt2]) * (rgt2);
//cout << lft2 << "\n";
res += (pre[rgt1 - 1] - pre[lft2]) * ext1;
ans.push_back(res);
}
return ans;
}
return {};
}
/*
____ ___ ___ ____ _____ ____ ____ ___
| | | | \ | | /| | | | \
| | | | | |____ | | | _ |____ |___/
| | | | | | | | | | | | \
|____ |___| |___/ |____ | __|__ |____| |____ | \
*/
