#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;
int n,q;
int t[5007][5007];
int len;
int row[5][MAXN],col[5][MAXN];
int prefrow[5][MAXN],prefcol[5][MAXN];
int seq[MAXN];
long long incr[MAXN],decr[MAXN],pref[MAXN];
vector<long long> sol;
int nand(int x,int y){
return x==0 and y==0;
}
long long diag(int from,int to,bool in){
if(in)return (incr[to]-incr[from-1]) - (pref[to]-pref[from-1])*(from-1);
else return (decr[from]-decr[to+1]) - (pref[to]-pref[from-1])*(len-1-to);
}
long long mult(int from,int to,long long c){
return (pref[to]-pref[from-1])*c;
}
int ff(int diff){
return n-diff-2;
}
long long calc(int from,int to,int l,int r){
int sq=min(to-from+1,r-l+1);
long long res=0;
res+=diag(ff(to-l),ff((to-sq+1)-l),true);
res+=diag(ff(from-(r-sq+1)),ff(from-r),false);
if(to-from+1>sq)res+=mult( ff((to-sq)-l) , ff((from+1)-l) , sq);
if(r-l+1>sq)res+=mult( ff(from-(l+1)) , ff(from-(r-sq)) , sq);
return res;
}
long long sum(int from,int to,int l,int r){
if(from>=3 and l>=3)return calc(from,to,l,r);
if(from<3 and to>=3)return sum(from,2,l,r) + sum(3,to,l,r);
if(l<3 and r>=3)return sum(from,to,l,2) + sum(from,to,3,r);
long long res=0;
if(to<=2){
res=prefrow[from][r] - prefrow[from][l-1];
if(from<to)res+=prefrow[to][r] - prefrow[to][l-1];
}else if(r<=2){
res=prefcol[l][to] - prefcol[l][from-1];
if(l<r)res+=prefcol[r][to] - prefcol[r][from-1];
}
return res;
}
vector<long long> mosaic(vector<int> X, vector<int> Y,vector<int> T, vector<int> B,vector<int> L, vector<int> R){
n=int(X.size());
q=int(T.size());
n=min(n,5000);
for(int i=1;i<=n;i++){
row[1][i]=X[i-1];
col[1][i]=Y[i-1];
t[1][i]=X[i-1]; t[i][1]=Y[i-1];
}
row[2][1]=col[1][2];
col[2][1]=row[1][2];
for(int i=2;i<=n;i++){
row[2][i]=nand(row[2][i-1],row[1][i]);
col[2][i]=nand(col[2][i-1],col[1][i]);
}
row[3][1]=col[1][3];
row[3][2]=col[2][3];
col[3][1]=row[1][3];
col[3][2]=row[2][3];
for(int i=3;i<=n;i++){
row[3][i]=nand(row[3][i-1],row[2][i]);
col[3][i]=nand(col[3][i-1],col[2][i]);
}
for(int i=1;i<=3;i++){
for(int f=1;f<=n;f++){
prefrow[i][f]=prefrow[i][f-1]+row[i][f];
prefcol[i][f]=prefcol[i][f-1]+col[i][f];
}
}
for(int i=n;i>=3;i--){
len++;
seq[len]=col[3][i];
}
for(int i=4;i<=n;i++){
len++;
seq[len]=row[3][i];
}
for(int i=1;i<=len;i++){
pref[i]=pref[i-1]+seq[i];
incr[i]=incr[i-1]+seq[i]*i;
}
for(int i=len;i>=1;i--){
decr[i]=decr[i+1]+seq[i]*(len-i+1);
}
for(int i=0;i<q;i++){
int from,to,l,r;
from=T[i]+1; to=B[i]+1;
l=L[i]+1; r=R[i]+1;
sol.push_back(sum(from,to,l,r));
}
return sol;
}
/*int main(){
//mosaic({1,1,1,0,0,0,1,1,0,1,0,1,1,1,0},{1,1,1,0,0,0,1,1,0,1,0,1,1,1,0},{},{},{},{});
auto y=mosaic({1, 0, 1, 0}, {1, 1, 0, 1}, {0, 2}, {3, 3}, {0, 0}, {3, 2});
for(auto s:y)cout<<s<<" ";
//auto yo=mosaic({0,0,0,0,0}, {0,0,0,0,0}, {1, 0}, {4, 3}, {2,0}, {4,3});
//for(auto s:yo)cout<<s<<" ";
return 0;
}*/
