#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];
void work0()
{
	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,tag[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<=now+n;i++) printf("%d ",tag[i]);printf("\n");
	for(int i=1;i<=q;i++)
	{
		if(qu[i]>qd[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-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();
	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
*/