#include "mosaic.h"
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
vl mosaic(vi X,vi Y,vi T,vi B,vi L,vi R) {
	const int D=20;
	int n=max(X.size(),Y.size()),q=max(L.size(),R.size());
	vector<vi> adj(2*n-1);
	for(int i=0;i<2*n;++i) adj[i].reserve(D+1);
	auto A=[&](int i,int j)->int&{
		int p=i-j+n-1,d=min(i,j);
		while(d>=(int)adj[p].size()) adj[p].emplace_back(0);
		return adj[p][d];
	};
	for(int i=0;i<n;++i)
		for(int j=0;j<n;++j){
			if(i>D&&j>D) break;
			if(!i||!j){
				if(!i) A(i,j)=X[j];
				if(!j) A(i,j)=Y[i];
				continue;
			}
			A(i,j)=!A(i-1,j)&&!A(i,j-1);
		}
	for(int i=0;i<n;++i)
		for(int j=0;j<n;++j){
			if(i>=D&&j>=D) break;
			if(i) A(i,j)+=A(i-1,j);
			if(j) A(i,j)+=A(i,j-1);
		}
	auto qry=[&](int x,int y)->ll{
		if(x<0||y<0) return 0;
		if(x>=D&&y>=D){
			ll ans=A(x,D-1)+A(D-1,y)-A(D-1,D-1);
			for(int i=D;i<=y;++i) // (D,i)
				if(A(D,i)) ans+=min(x-D,y-i)+1;
			for(int i=D+1;i<=x;++i) // (i,D)
				if(A(i,D)) ans+=min(x-i,y-D)+1;
			return ans;
		}
		else return A(x,y);
	};
	vl res(q);
	for(int o=0;o<q;++o){
		--T[o];--L[o];
		res[o]=qry(B[o],R[o])+qry(T[o],L[o])-qry(T[o],R[o])-qry(B[o],R[o]);
	}
	return res;
}