#include "mosaic.h"
#include<iostream>
#include<cstdio>
#include<vector>
#define N 200000
using namespace std;
int n,s[N+1],s2[N+1],s3[N+1],s4[N+1],s5[N+1],s6[N+1];
long long s7[N+1],s8[N+1];
int calc(int x,int y)
{
	return (!x)&&(!y);
}
vector<int>p[N+1];
long long solve(int x,int y)
{
	if (x<0||y<0) return 0;
	long long res=0;
	if (x>=0) res+=s[y];
	if (y>=0) res+=s2[x];
	if (x>=1) res+=s3[y];
	if (y>=1) res+=s4[x];
	if (x>=2)
	{
		int ps=max(y-(x-2),1);
		res+=1ll*s5[ps]*(x-1)+1ll*(s5[n-1]-s5[ps])*(y+1)-(s7[n-1]-s7[ps]);
	}
	if (y>=2)
	{
		int ps=max(x-(y-2),1);
		res+=1ll*s6[ps]*(y-1)+1ll*(s6[n-1]-s6[ps])*(x+1)-(s8[n-1]-s8[ps]);
	}
	return res;
}
std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y,
                              std::vector<int> T, std::vector<int> B,
                              std::vector<int> L, std::vector<int> R){
	vector<long long>C(T.size());
	n=X.size();
	for (int i=0;i<n;++i)
	{
		if (i<=2) p[i].resize(n);
		else p[i].resize(3);
	}
	for (int i=0;i<n;++i) p[0][i]=X[i],p[i][0]=Y[i];
	for (int i=1;i<n;++i)
		for (int j=1;j<((i<=2)?n:3);++j)
			p[i][j]=calc(p[i-1][j],p[i][j-1]);
	s[0]=p[0][0];
	for (int i=1;i<n;++i) s[i]=s[i-1]+p[0][i],s2[i]=s2[i-1]+p[i][0];
	if (n>=2)
	{
		s3[1]=p[1][1];
		for (int i=2;i<n;++i) s3[i]=s3[i-1]+p[1][i],s4[i]=s4[i-1]+p[i][1];
	}
	if (n>=3)
	{
		s5[2]=p[2][2];
		for (int i=3;i<n;++i) s5[i]=s5[i-1]+p[2][i],s6[i]=s6[i-1]+p[i][2];
		s7[2]=p[2][2]*2ll;
		for (int i=3;i<n;++i) s7[i]=s7[i-1]+1ll*p[2][i]*i,s8[i]=s8[i-1]+1ll*p[i][2]*i;
	}
	for (int i=0;i<T.size();++i) C[i]=solve(B[i],R[i])-solve(T[i]-1,R[i])-solve(B[i],L[i]-1)+solve(T[i]-1,L[i]-1);
	return C;
}