#include <bits/stdc++.h>
#include "mosaic.h"
using namespace std;

int n,Q;
int sX[200010],sY[200010];
int secX[200010],secY[200010];
int thdX[200010],thdY[200010];

int col[400010],top,tk,tk_;
long long sum[400010];

inline long long calc(int X0,int Y0)
{
	if(X0>1&&Y0>1)
	{
		if(Y0>=X0)
		{
			tk=upper_bound(col+1,col+top+1,X0)-col-1;
			return 1ll*tk*X0-sum[tk];
		}
		else
		{
			tk=upper_bound(col+1,col+top+1,X0)-col-1;
			tk_=upper_bound(col+1,col+top+1,X0-Y0+1)-col-1;
			return 1ll*(tk-tk_)*X0-(sum[tk]-sum[tk_])+1ll*tk_*(Y0-1);
		}
	}else return 0;
}

vector<long long> mosaic(vector<int> X,vector<int> Y,vector<int> T,vector<int> B,vector<int> L,vector<int> R)
{
	swap(X,Y);
	vector<long long> ans;
	n=X.size(),Q=T.size();
	ans.resize(Q);

	secX[1]=secY[1]=!(X[1]|Y[1]);
	for(int i=2;i<n;i++) secX[i]=!(secX[i-1]|X[i]);
	for(int i=2;i<n;i++) secY[i]=!(secY[i-1]|Y[i]);

	thdX[2]=thdY[2]=!(secX[2]|secY[2]);
	for(int i=3;i<n;i++) thdX[i]=!(thdX[i-1]|secX[i]);
	for(int i=3;i<n;i++) thdY[i]=!(thdY[i-1]|secY[i]);

	for(int i=2;i<n;i++) if(thdX[i]) col[++top]=i-1;
	for(int i=1;i<=top;i++) sum[i]=sum[i-1]+col[i];
	for(int i=0;i<Q;i++)
	{
		ans[i]+=calc(B[i],R[i]);
		ans[i]-=calc(T[i]-1,R[i]);
		ans[i]-=calc(B[i],L[i]-1);
		ans[i]+=calc(T[i]-1,L[i]-1);
	}

	top=0;
	for(int i=3;i<n;i++) if(thdY[i]) col[++top]=i-1;
	for(int i=1;i<=top;i++) sum[i]=sum[i-1]+col[i];
	for(int i=0;i<Q;i++)
	{
		ans[i]+=calc(R[i],B[i]);
		ans[i]-=calc(R[i],T[i]-1);
		ans[i]-=calc(L[i]-1,B[i]);
		ans[i]+=calc(L[i]-1,T[i]-1);
	}

	sX[0]=X[0];
	for(int i=1;i<n;i++)
		sX[i]=X[i]+sX[i-1],sY[i]=Y[i]+sY[i-1];
	for(int i=0;i<Q;i++)
	{
		if(!L[i])
		{
			ans[i]+=sX[B[i]];
			if(T[i]) ans[i]-=sX[T[i]-1];
		}
		if(!T[i])
		{
			ans[i]+=sY[R[i]];
			if(L[i]) ans[i]-=sY[L[i]-1];
		}
	}

	secY[1]=0;
	sX[0]=sY[0]=0;
	for(int i=1;i<n;i++)
		sX[i]=sX[i-1]+secX[i],sY[i]=sY[i-1]+secY[i];
	for(int i=0;i<Q;i++)
	{
		if(L[i]<=1&&R[i]>=1)
		{
			ans[i]+=sX[B[i]];
			if(T[i]) ans[i]-=sX[T[i]-1];
		}
		if(T[i]<=1&&B[i]>=1)
		{
			ans[i]+=sY[R[i]];
			if(L[i]) ans[i]-=sY[L[i]-1];
		}
	}
	return ans;
}