#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long,long long>
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define pb push_back
#define sz(x) (int)(x).size()
#define rsz resize
#define ass assign
#define F(i,l,r) for(int i=(l);i<(r);++i)
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define each(a,x) for(auto a:x)
#define FOR(i,a) for(int i=0;i<(a);i++)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define eb emplace_back
#define ft front()
#define V vector
#include "mosaic.h"
struct PrefSum{
V<ll> p;
PrefSum(){}
PrefSum(const V<int>& a){
int n=sz(a);
p.ass(n+1,0);
FOR(i,n)p[i+1]=p[i]+a[i];
}
ll query(int l,int r){
if(l>r)return 0;
return p[r+1]-p[l];
}
};
V<ll> mosaic(V<int> X,V<int> Y,V<int> T,V<int> B,V<int> L,V<int> R){
int n=sz(X),q=sz(T);
V<ll> res(q);
if(n<=5000){
V<V<int>> grid(n,V<int>(n));
FOR(i,n)grid[0][i]=X[i];
FOR(i,n)grid[i][0]=Y[i];
F(i,1,n){
F(j,1,n)grid[i][j]=(!grid[i-1][j] && !grid[i][j-1]);
}
V<V<ll>> ps(n+1,V<ll>(n+1,0));
F(i,1,n+1){
F(j,1,n+1)ps[i][j]=grid[i-1][j-1]+ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1];
}
FOR(k,q)res[k]=ps[B[k]+1][R[k]+1]-ps[T[k]][R[k]+1]-ps[B[k]+1][L[k]]+ps[T[k]][L[k]];
return res;
}
bool sub5=1;
FOR(i,n){
if(X[i]!=0 || Y[i]!=0){
sub5=0;
break;
}
}
if(sub5){
FOR(k,q){
ll t=max(1,T[k]),b=B[k],l=max(1,L[k]),r=R[k];
if(t>b || l>r){
res[k]=0;
continue;
}
ll h=b-t+1,w=r-l+1;
res[k]=(h*w)/2;
if((h*w)&1 && (t+l)%2==0)res[k]++;
}
return res;
}
V<int> r1(n),r2(n),c1(n),c2(n);
r1[0]=Y[1];
F(j,1,n)r1[j]=(!X[j] && !r1[j-1]);
r2[0]=Y[2];
F(j,1,n)r2[j]=(!r1[j] && !r2[j-1]);
c1[0]=X[1];
F(i,1,n)c1[i]=(!Y[i] && !c1[i-1]);
c2[0]=X[2];
F(i,1,n)c2[i]=(!c1[i] && !c2[i-1]);
PrefSum psr0(X),psr1(r1),psr2(r2),psc1(c1),psc2(c2);
FOR(k,q){
if(T[k]==B[k]){
int r=T[k],l=L[k],rr=R[k];
if(!r)res[k]=psr0.query(l,rr);
else if(r==1)res[k]=psr1.query(l,rr);
else{
ll tot=0;
if(!l){
tot+=Y[r];
l++;
}
if(l==1 && l<=rr){
tot+=c1[r];
l++;
}
if(l<=rr){
int hi=min(rr,r-1);
if(l<=hi)tot+=psc2.query(r-hi+2,r-l+2);
int lo=max(l,r);
if(lo<=rr)tot+=psr2.query(lo-r+2,rr-r+2);
}
res[k]=tot;
}
}else res[k]=0;
}
return res;
}
