#include "mosaic.h"
#include <bits/stdc++.h>
#define int long long
#define si signed
using namespace std;
const int NR=2e5+15;
const int M=10;
int n,v[15][15],a1[NR][15],a2[15][NR],pre1[NR][15],pre2[15][NR],val[NR*2],s0[NR*2],s1[NR*2];

int calc0(int l,int r){return s0[r]-s0[l-1];}
int calc1(int l,int r){return s1[r]-s1[l-1];}
int calc(int l,int r,int k){
	int v1=calc1(l,l+k-1)-(l-1)*calc0(l,l+k-1);
	int v2=(r+1)*calc0(r-k+1,r)-calc1(r-k+1,r);
	int con=calc0(l+k,r-k)*(k+1);
	return v1+v2+con;
}
vector<int> mosaic(vector<si> X, vector<si> Y,
                              vector<si> T, vector<si> B,
                              vector<si> L, vector<si> R) {
	n=X.size();
	for(int i=0;i<n;i++)a2[0][i]=X[i],a1[i][0]=Y[i];
	for(int i=0;i<M;i++)v[0][i]=a2[0][i],v[i][0]=a1[i][0];
	for(int i=1;i<M;i++)
		for(int j=1;j<M;j++)
			v[i][j]=!(v[i-1][j]|v[i][j-1]);
	for(int i=0;i<M;i++)
		for(int j=0;j<M;j++)
			a1[i][j]=a2[i][j]=v[i][j];
	for(int i=M;i<n;i++)
		for(int j=1;j<M;j++)a1[i][j]=!(a1[i-1][j]|a1[i][j-1]);
	for(int i=1;i<M;i++)
		for(int j=M;j<=n;j++)a2[i][j]=!(a2[i-1][j]|a2[i][j-1]);
	for(int i=0;i<=n;i++)
		for(int j=0;j<M;j++)
			pre1[i][j]=a1[i][j]+((i>0)?pre1[i-1][j]:0);
	for(int i=0;i<M;i++)
		for(int j=0;j<=n;j++)
			pre2[i][j]=a2[i][j]+((j>0)?pre2[i][j-1]:0);
//	for(int i=0;i<M;i++){
//		for(int j=0;j<M;j++)cout<<pre1[i][j]<<' ';
//		cout<<endl; 
//	}
	for(int i=M;i<=n;i++)
		val[(M-1)-i+n]=a2[M-1][i],val[i-(M-1)+n]=a1[i][M-1];
	val[n]=v[M-1][M-1];
	for(int i=1;i<=2*n;i++)
		s0[i]=s0[i-1]+val[i],s1[i]=s1[i-1]+val[i]*i;
	int q=T.size();
	vector<int>ans;
	for(int i=0;i<q;i++){
		int u=T[i],d=B[i],l=L[i],r=R[i],res=0;
		for(int i=l;i<=min(M-1,r);i++){
			if(u)res+=pre1[d][i]-pre1[u-1][i];
			else res+=pre1[d][i];
		}
		l=max(l,M);
		if(u>d||l>r){
			ans.push_back(res);
			continue;
		}
		for(int i=u;i<=min(M-1,d);i++){
			if(u)res+=pre2[i][r]-pre2[i][l-1];
			else res+=pre2[i][r];
		}
		u=max(u,M);
		if(u>d||l>r){
			ans.push_back(res);
			continue;
		}
		int k=min(r-l,d-u);
		res+=calc(u-r+n,d-l+n,k);
		ans.push_back(res);
	}
	return ans;
}