#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"
ll count_parity(ll L,ll R,int parity){
if(L>R)return 0;
auto f=[&](ll n,int p) {
if(n<0)return 0LL;
if(!p)return n/2+1;
return (n+1)/2;
};
return f(R,parity)-f(L-1,parity);
}
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);
bool zeroXY=1;
each(x,X){
if(x!=0)zeroXY=0;
}
each(y,Y){
if(y!=0)zeroXY=0;
}
if(n<=5000){
V<V<int>> grid(n,V<int>(n));
V<V<ll>> ps(n+1,V<ll>(n+1,0));
FOR(i,n){
FOR(j,n){
if(!i)grid[i][j]=X[j];
else if(!j)grid[i][j]=Y[i];
else grid[i][j]=(!grid[i-1][j] && !grid[i][j-1]);
ps[i+1][j+1]=grid[i][j]+ps[i][j+1]+ps[i+1][j]-ps[i][j];
}
}
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]];
}else if(zeroXY){
FOR(k,q){
ll t=T[k],b=B[k],l=L[k],r=R[k];
ll tprime=max(1LL,t),lprime=max(1LL,l);
if(tprime>b || lprime>r)res[k]=0;
else{
ll row_evens=count_parity(tprime,b,0);
ll row_odds=count_parity(tprime,b,1);
ll col_evens=count_parity(lprime,r,0);
ll col_odds=count_parity(lprime,r,1);
res[k]=(row_evens*col_evens)+(row_odds*col_odds);
}
}
}else{
V<ll> psx(n+1,0);
FOR(i,n)psx[i+1]=psx[i]+X[i];
FOR(k,q){
if(!T[k] && !B[k])res[k]=psx[R[k]+1]-psx[L[k]];
else res[k]=0;
}
}
return res;
}
