#include "bits/stdc++.h"
// #include "grader.cpp"
#include "mosaic.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
#define mm make_pair
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
vector<ll> mosaic(vector<int> x, vector<int> y, vector<int> T, vector<int> B, vector<int> L, vector<int> R){
map<pii, bool> mp;
int n=(int)x.size();
for(int j = 1; j <= n; ++j)
mp[{1, j}]=x[j-1];
for(int i = 1; i <= n; ++i)
mp[{i, 1}]=y[i-1];
for(int i = 2; i <= 3; ++i)
for(int j = 2; j <= n; ++j)
if(mp[{i, j-1}]+mp[{i-1, j}]==0)
mp[{i, j}]=1;
for(int i = 4; i <= n; ++i)
for(int j = 2; j <= 3; ++j)
if(mp[{i, j-1}]+mp[{i-1, j}]==0)
mp[{i, j}]=1;
vector<vector<int>> prow(3, vector<int> (n+1, 0));
for(int i = 1; i <= 2; ++i)
for(int j = 1; j <= n; ++j)
prow[i][j]=prow[i][j-1]+mp[{i, j}];
vector<vector<int>> pcol(3, vector<int> (n+1, 0));
for(int j = 1; j <= 2; ++j)
for(int i = 1; i <= n; ++i)
pcol[j][i]=pcol[j][i-1]+mp[{i, j}];
map<int, int> ind;
vector<int> a(2*n), sum(2*n);
vector<ll> mul(2*n);
int id=0;
for(int i = n; i >= 3; --i){
if(i>3){
ind[i-3]=++id;
a[id]=mp[{i, 3}];
continue;
}
for(int j = 3; j <= n; ++j)
ind[3-j]=++id, a[id]=mp[{3, j}];
}
for(int i = 1; i < 2*n; ++i)
sum[i]=sum[i-1]+a[i], mul[i]=mul[i-1]+a[i]*1ll*i;
auto calc=[&](int l, int r, bool dir) -> ll {
if(l>r)
return 0;
if(!dir){
ll Left=mul[r]-mul[l-1], Right=(l-1)*1ll*(sum[r]-sum[l-1]);
return Left-Right;
}
ll Left=(r+1)*1ll*(sum[r]-sum[l-1]), Right=mul[r]-mul[l-1];
return Left-Right;
};
vector<ll> ans((int)T.size());
for(int ad = 0; ad < (int)T.size(); ++ad){
int x=T[ad]+1, y=L[ad]+1, x2=B[ad]+1, y2=R[ad]+1;
ll answer=0;
if(n<=2){
for(int i = x; i <= x2; ++i)
for(int j = y; j <= y2; ++j)
answer+=mp[{i, j}];
ans[ad]=answer;
continue;
}
if(x<=2)
answer+=prow[2][y2]-prow[2][y-1];
if(x<=1)
answer+=prow[1][y2]-prow[1][y-1];
umax(x, 3);
if(x>x2){
ans[ad]=answer;
continue;
}
if(y<=2)
answer+=pcol[2][x2]-pcol[2][x-1];
// printf("%d %d %d %d\n", x, y, x2, y2);wr;
// printf("%lld\n", answer);wr;
if(y<=1)
answer+=pcol[1][x2]-pcol[1][x-1];
umax(y, 3);
if(y>y2){
ans[ad]=answer;
continue;
}
int n2=x2-x+1, m2=y2-y+1;
int sz=n2+m2-1, len=min(m2, n2);
if(n2>m2){
// (1,1) point is maxi's end point
int maxir=ind[x-y], maxil=ind[x2-y2];
int l1=ind[x2-y], r1=maxil-1;
int l2=maxir+1, r2=l1+sz-1;
answer+=calc(l1, r1, 0);
answer+=(sum[maxir]-sum[maxil-1])*1ll*len;
answer+=calc(l2, r2, 1);
}
else{
// (1,1) point is maxi's start point
int maxil=ind[x-y], maxir=ind[x2-y2];
int l1=ind[x2-y], r1=maxil-1;
int l2=maxir+1, r2=l1+sz-1;
answer+=calc(l1, r1, 0);
answer+=(sum[maxir]-sum[maxil-1])*1ll*len;
answer+=calc(l2, r2, 1);
}
ans[ad]=answer;
}
return ans;
}
