#include<bits/stdc++.h>
using namespace std;
const int N=400005;
int n,q;
int a[N],b[N],val[N];
long long sum[N],sum2[N];
int tag[N],sumtag[N];
//tag:cnt of added "000"->"010"
int qu[N],qd[N],ql[N],qr[N];
long long ans[N];
namespace sol
{
	const int M=5005;
	int val[M][M];
	int sum[M][M];
	void workn2()
	{
		for(int i=1;i<=n;i++) val[1][i]=a[i];
		for(int i=1;i<=n;i++) val[i][1]=b[i];
		for(int i=2;i<=n;i++)
			for(int j=2;j<=n;j++) val[i][j]=(val[i-1][j]^1)&(val[i][j-1]^1);
//		for(int i=1;i<=n;i++){
//			for(int j=1;j<=n;j++) printf("%d",val[i][j]);printf("\n");}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++) sum[i][j]=val[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
		for(int i=1;i<=q;i++) ans[i]=sum[qd[i]][qr[i]]-sum[qu[i]-1][qr[i]]-sum[qd[i]][ql[i]-1]+sum[qu[i]-1][ql[i]-1];
	}
}
void work0()
{
	for(int i=1;i<=n;i++) val[i]=b[i];
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+val[i];
	for(int i=1;i<=q;i++) if(ql[i]==1) ans[i]+=sum[qd[i]]-sum[qu[i]-1],ql[i]++;
//	for(int i=1;i<=n;i++) printf("%d ",val[i]);printf("\n");
	val[1]=a[2];
	for(int i=2;i<=n;i++) val[i]=(val[i-1]^1)&(val[i]^1);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+val[i];
	for(int i=1;i<=q;i++) if(ql[i]==2&&qr[i]>=2) ans[i]+=sum[qd[i]]-sum[qu[i]-1],ql[i]++;
//	for(int i=1;i<=n;i++) printf("%d ",val[i]);printf("\n");
	
	for(int i=1;i<=n;i++) val[i]=a[i];
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+val[i];
	for(int i=1;i<=q;i++) if(qu[i]==1) ans[i]+=sum[qr[i]]-sum[ql[i]-1],qu[i]++;
//	for(int i=1;i<=n;i++) printf("%d ",val[i]);printf("\n");
	val[1]=b[2];
	for(int i=2;i<=n;i++) val[i]=(val[i-1]^1)&(val[i]^1);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+val[i];
	for(int i=1;i<=q;i++) if(qu[i]==2&&qd[i]>=2) ans[i]+=sum[qr[i]]-sum[ql[i]-1],qu[i]++;
//	for(int i=1;i<=n;i++) printf("%d ",val[i]);printf("\n");
	val[1]=b[3];
	for(int i=2;i<=n;i++) val[i]=(val[i-1]^1)&(val[i]^1);
}
void work1()
{
	int now=n-3;
	for(int i=n;i>=1;i--) val[now+i]=val[i];
	for(int i=4;i<=n;i++)
	{
		int x=now-i+4;
		val[x]=b[i];
		if(val[x]==0&&val[x+1]==0&&b[i+1]==0&&i!=n) val[x]=1;
	}
	for(int i=1;i<=now+n;i++) sum[i]=sum[i-1]+val[i];
	for(int i=1;i<=now+n;i++) sum2[i]=sum2[i-1]+sum[i];
//	for(int i=1;i<=now+n;i++) printf("%d ",val[i]);printf("\n");
//	for(int i=1;i<=now+n;i++) printf("%lld ",sum[i]);printf("\n");
//	for(int i=1;i<=now+n;i++) printf("%lld ",sum2[i]);printf("\n");
	for(int i=1;i<=q;i++)
	{
		if(qu[i]>qd[i]||ql[i]>qr[i]) continue;
		int l=ql[i]-(qu[i]-2)+1+now,r=qr[i]-(qu[i]-2)+1+now;
		int len=qd[i]-qu[i]+1;
//		printf("%d:%d %d %d::",i,l,r,len);
//		printf("%lld ",ans[i]);
		ans[i]+=sum2[r]-sum2[l-1]-sum2[r-len]+sum2[l-1-len];
//		printf("%lld\n",ans[i]);
	}
}
vector <long long> mosaic(vector <int> X,vector <int> Y,vector <int> T,vector <int> B,vector <int> L,vector <int> R)
{
	n=X.size();
	for(int i=0;i<n;i++) a[i+1]=X[i],b[i+1]=Y[i];
	q=T.size();
	for(int i=0;i<q;i++) qu[i+1]=T[i]+1,qd[i+1]=B[i]+1,ql[i+1]=L[i]+1,qr[i+1]=R[i]+1;
//	work0();
//	work1();
	sol::workn2();
	vector <long long> ret;
	for(int i=1;i<=q;i++) ret.push_back(ans[i]);
	return ret;
}
/*
4
1 0 1 0
1 1 0 1
2
0 3 0 3
2 3 0 2

7
3


5
0 1 1 1 1
0 0 0 0 0
2
1 4 0 4
0 4 0 3
*/