#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);
			if(i&&j) A(i,j)-=A(i-1,j-1);
		}
	vi sx(n),sy(n);
	for(int i=D;i<n;++i) sx[i]=sx[i-1]+A(D,i);
	for(int i=D+1;i<n;++i) sy[i]=sy[i-1]+A(i,D);
	vl tx(n),ty(n);
	for(int i=D;i<n;++i) tx[i]=tx[i-1]+A(D,i)*i;
	for(int i=D+1;i<n;++i) ty[i]=ty[i-1]+A(i,D)*i;
	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);
			if(y>=x) ans+=(ll)sx[min(D+y-x,n-1)]*(x-D+1);
			else ans+=(ll)sy[min(D+x-y,n-1)]*(y-D+1);
			int ox=max(D-1,D+y-x),oy=max(D,D+x-y);
			ans+=(ll)(sx[y]-sx[ox])*(y+1)-(tx[y]-tx[ox]);
			ans+=(ll)(sy[y]-sy[oy])*(x+1)-(ty[x]-ty[oy]);
			// for(int i=ox+1;i<=y;++i) // (D,i)
				// if(A(D,i)) ans-=i;
			// for(int i=oy+1;i<=x;++i) // (i,D)
				// if(A(i,D)) ans-=i;
			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],L[o]);
	}
	return res;
}