#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
using namespace std;
using ll = long long;
const ll N = 4e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 , mod = 1e9+7;
unordered_map<ll,ll> dp[N] , pr[N];
ll pref[N] , suf[N] , sum[N];
ll get(ll a , ll b , ll c , ll d){
c--;
d--;
return pr[a][b]-pr[a][d]-pr[c][b]+pr[c][d];
}
vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
ll n = X.size();
for(ll i = 1; i <= n; i++){
dp[1][i] = X[i-1];
dp[i][1] = Y[i-1];
}
for(ll i = 1; i <= n; i++){
for(ll j = 1; j <= n; j++){
if(i == 1 || j == 1) continue;
if(i > 3 && j > 3) break;
if(dp[i-1][j] == 0 && dp[i][j-1] == 0) dp[i][j] = 1;
else dp[i][j] = 0;
}
}
for(ll i = 1; i <= n; i++){
for(ll j = 1; j <= n; j++){
if(i > 3 && j > 3) break;
pr[i][j] = dp[i][j] + pr[i][j-1] + pr[i-1][j] - pr[i-1][j-1];
}
}
set<pair<ll,ll>> st;
for(ll j = 3 , i = 3; j <= n; j++){
st.insert({j-i,dp[i][j]});
}
for(ll i = 3 , j = 3; i <= n; i++){
st.insert({j-i,dp[i][j]});
}
vector<ll> vec;
vec.push_back(0);
map<ll,ll> ind;
for(auto it : st) {
ind[it.F] = vec.size();
vec.push_back(it.S);
}
for(ll i = 1; i < vec.size(); i++){
pref[i] = pref[i-1] + vec[i]*i;
sum[i] = sum[i-1]+vec[i];
}
for(ll i = vec.size()-1; i >= 1; i--){
suf[i] = suf[i+1] + vec[i]*(vec.size()-i);
}
ll q = (ll)T.size();
vector<long long> C(q, 0);
for(ll i = 0; i < q; i++){
B[i]++;
R[i]++;
T[i]++;
L[i]++;
if(R[i] <= 3 || B[i] <= 3){
C[i] = get(B[i],R[i],T[i],L[i]);
} else {
ll ans = 0;
while(L[i] < 3){
ans += get(B[i],L[i],T[i],L[i]);
L[i]++;
}
while(T[i] < 3){
ans += get(T[i],R[i],T[i],L[i]);
T[i]++;
}
ll mn = min(B[i]-T[i]+1 , R[i]-L[i]+1);
ll lin = ind[L[i]-B[i]] , rin = ind[R[i]-T[i]];
C[i] = ((pref[lin+mn-2]-pref[lin-1])-(sum[lin+mn-2]-sum[lin-1])*(lin-1))
+ ((suf[rin-mn+2]-suf[rin+1])-(sum[rin]-sum[rin-mn+1])*(vec.size()-rin-1))
+ ans
+ (sum[rin-mn+1] - sum[lin+mn-2]) * mn;
// cout << lin << " " << lin+mn-2 << "\n";
// cout << (pref[lin+mn-2]-pref[lin-1]) <<" " << (sum[lin+mn-2]-sum[lin-1])*(lin-1) <<" " << mn <<" " << ans << "\n";
}
}
return C;
}
// int main() {
// int N;
// assert(1 == scanf("%d", &N));
// std::vector<int> X(N), Y(N);
// for (int i = 0; i < N; i++)
// assert(1 == scanf("%d", &X[i]));
// for (int i = 0; i < N; i++)
// assert(1 == scanf("%d", &Y[i]));
// int Q;
// assert(1 == scanf("%d", &Q));
// std::vector<int> T(Q), B(Q), L(Q), R(Q);
// for (int k = 0; k < Q; k++)
// assert(4 == scanf("%d%d%d%d", &T[k], &B[k], &L[k], &R[k]));
// fclose(stdin);
//
// std::vector<long long> C = mosaic(X, Y, T, B, L, R);
//
// int S = (int)C.size();
// for (int k = 0; k < S; k++)
// printf("%lld\n", C[k]);
// fclose(stdout);
//
// return 0;
// }
