#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];
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)
	{
		for (int i=2;i<=y;++i)
			if (p[2][i])
				res+=min(x-2+1,y-i+1);
	}
	if (y>=2)
	{
		for (int i=3;i<=x;++i)
			if (p[i][2])
				res+=min(x-i+1,y-2+1);
	}
	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].push_back(n);
		else p[i].push_back(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];
	}
	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;
}