#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=400010;
vector <ll> rez;
ll n,q,l[MAXN],c[MAXN],l2[MAXN],c2[MAXN],l3[MAXN],c3[MAXN];
ll sl1[MAXN],sl2[MAXN],sc1[MAXN],sc2[MAXN];
ll d[MAXN],s[MAXN],s1[MAXN],s2[MAXN];
struct query{
ll x1,y1,x2,y2;
ll s;
}v[MAXN];
ll f (ll x1, ll y1, ll x2, ll y2){
if (x1==x2 and y1==y2) return d[x1-y1+n-2];
int d1=x1-y2+n-2,d2=x2-y1+n-2;
ll crt=min (x2-x1,y2-y1);
if (crt==0) return s[d2]-s[d1-1];
ll rez=0;
rez+=s1[d1+crt-1]-s1[d1-1]-(s[d1+crt-1]-s[d1-1])*(d1-1);
//int cf=max (x2-x1,y2-y1)-crt+1;
rez+=1LL*(crt+1)*(s[d2-crt]-s[d1+crt-1]);
rez+=s2[d2-crt+1]-s2[d2+1]-(s[d2]-s[d2-crt])*(2*n-5-d2);
return rez;
}
void solve (){
l2[1]=c[2];
for (int i=2;i<=n;++i){
if (l2[i-1]==l[i] and l[i]==0) l2[i]=1;
else l2[i]=0;
}
c2[1]=l[2];
for (int i=2;i<=n;++i){
if (c2[i-1]==c[i] and c[i]==0) c2[i]=1;
else c2[i]=0;
}
for (int i=1;i<=n;++i){
sl1[i]=sl1[i-1]+l[i];
sl2[i]=sl2[i-1]+l2[i];
sc1[i]=sc1[i-1]+c[i];
sc2[i]=sc2[i-1]+c2[i];
}
for (int i=1;i<=q;++i){
if (v[i].x1==1){
v[i].s+=sl1[v[i].y2]-sl1[v[i].y1-1];
v[i].x1++;
}
if (v[i].x1==2 and v[i].x1<=v[i].x2){
v[i].s+=sl2[v[i].y2]-sl2[v[i].y1-1];
v[i].x1++;
}
if (v[i].y1==1){
v[i].s+=sc1[v[i].x2]-sc1[v[i].x1-1];
v[i].y1++;
}
if (v[i].y1==2 and v[i].y1<=v[i].y2){
v[i].s+=sc2[v[i].x2]-sc2[v[i].x1-1];
v[i].y1++;
}
}
if (l2[3]==c2[3] and l2[3]==0) l3[3]=1;
else l3[3]=0;
for (int i=4;i<=n;++i){
if (l3[i-1]==l2[i] and l2[i]==0) l3[i]=1;
else l3[i]=0;
}
if (l2[3]==c2[3] and c2[3]==0) c3[3]=1;
else c3[3]=0;
for (int i=4;i<=n;++i){
if (c3[i-1]==c2[i] and c2[i]==0) c3[i]=1;
else c3[i]=0;
}
for (int i=3;i<=n;++i){
d[3-i+n-2]=l3[i];
}
for (int i=4;i<=n;++i){
d[i-3+n-2]=c3[i];
}
for (int i=1;i<=2*n-5;++i){
s[i]=s[i-1]+d[i];
s1[i]=s1[i-1]+1LL*i*d[i];
}
for (int i=2*n-5;i>=1;--i){
s2[i]=s2[i+1]+1LL*(2*n-5-i+1)*d[i];
}
for (int i=1;i<=q;++i){
if (v[i].x1>v[i].x2) continue;
if (v[i].y1>v[i].y2) continue;
v[i].s+=f (v[i].x1,v[i].y1,v[i].x2,v[i].y2);
}
for (int i=1;i<=q;++i){
rez.push_back (v[i].s);
}
}
vector<ll> mosaic(vector<int> x, vector<int> y,vector<int> x1, vector<int> x2,vector<int> y1, vector<int> y2){
n=x.size ();
q=x1.size ();
for (int i=0;i<n;++i){
l[i+1]=x[i];
c[i+1]=y[i];
}
for (int i=0;i<q;++i){
x1[i]++;
x2[i]++;
y1[i]++;
y2[i]++;
v[i+1]={x1[i],y1[i],x2[i],y2[i]};
}
solve ();
return rez;
}
