#include <bits/stdc++.h>
using namespace std;
vector<long long>subtask3(vector<int>&X,vector<int>&Y,vector<int>&T,vector<int>&B,vector<int>&L,vector<int>&R){
int n=X.size();
vector<int>sp(n+5,0);
int i;
for(i=1;i<=n;++i)
sp[i]=sp[i-1]+X[i-1];
int q=T.size();
vector<long long>answer;
for(i=0;i<q;++i){
int left=L[i]+1;
int right=R[i]+1;
answer.push_back(sp[right]-sp[left-1]);
}
return answer;
}
vector<long long>subtask4(vector<int>&X,vector<int>&Y,vector<int>&T,vector<int>&B,vector<int>&L,vector<int>&R){
int n=X.size();
vector<vector<bool>>mat(n+5,vector<bool>(n+5,0));
vector<vector<int>>sp(n+5,vector<int>(n+5,0));
int i,j;
for(j=1;j<=n;++j)
mat[1][j]=X[j-1];
for(i=1;i<=n;++i)
mat[i][1]=Y[i-1];
for(i=2;i<=n;++i)
for(j=2;j<=n;++j)
mat[i][j]=((!mat[i-1][j] && !mat[i][j-1])?1:0);
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
sp[i][j]=sp[i-1][j]+sp[i][j-1]-sp[i-1][j-1]+mat[i][j];
vector<long long>answer;
int q=T.size();
for(i=0;i<q;++i){
int top=T[i]+1;
int bottom=B[i]+1;
int left=L[i]+1;
int right=R[i]+1;
answer.push_back(sp[bottom][right]-sp[bottom][left-1]-sp[top-1][right]+sp[top-1][left-1]);
}
return answer;
}
vector<long long>subtask5(vector<int>&X,vector<int>&Y,vector<int>&T,vector<int>&B,vector<int>&L,vector<int>&R){
int q=T.size();
int i;
vector<long long>answer;
for(i=0;i<q;++i){
int top=T[i];
int bottom=B[i];
int left=L[i];
int right=R[i];
top=max(top,1);
left=max(left,1);
if(top>bottom || left>right)
answer.push_back(0);
else{
long long arie=1LL*(bottom-top+1)*(right-left+1);
int first_val=(top+left+1)%2;
if(arie&1 && first_val)
answer.push_back(arie/2+1);
else
answer.push_back(arie/2);
}
}
return answer;
}
int get_diag(int x,int y,int n){
return n-x+y;
}
vector<long long>subtask6(vector<int> X, vector<int> Y, vector<int> T, vector<int> B,vector<int> L, vector<int> R){
int n=X.size();
vector<bool>lin[3];
vector<bool>col[3];
int i;
for(i=0;i<3;++i){
lin[i].resize(n+5,0);
col[i].resize(n+5,0);
}
for(i=0;i<n;++i)
lin[0][i]=X[i];
for(i=0;i<n;++i)
col[0][i]=Y[i];
lin[1][0]=col[0][1];
lin[2][0]=col[0][2];
col[1][0]=lin[0][1];
col[2][0]=lin[0][2];
for(i=1;i<n;++i){
lin[1][i]=(!lin[1][i-1] && !lin[0][i])?1:0;
lin[2][i]=(!lin[2][i-1] && !lin[1][i])?1:0;
col[1][i]=(!col[1][i-1] && !col[0][i])?1:0;
col[2][i]=(!col[2][i-1] && !col[1][i])?1:0;
}
vector<bool>diag(2*n+5,0);
for(i=2;i<n;++i)
if(lin[2][i])
diag[get_diag(2,i,n)]=1;
for(i=2;i<n;++i)
if(col[2][i])
diag[get_diag(i,2,n)]=1;
int q=T.size();
vector<long long>answer;
for(i=0;i<q;++i){
int l=T[i];
int c=L[i];
if(l<3){
answer.push_back(lin[l][c]);
}
else
if(c<3){
answer.push_back(col[c][l]);
}
else{
answer.push_back(diag[get_diag(l,c,n)]);
}
}
return answer;
}
int bin_search(vector<int>&diag,int val){
///prima val care il intrece sau e egal
int l=-1,r=diag.size()-1;
/// (l r]
while(r-l>1){
int mid=(l+r)/2;
if(diag[mid]>=val)
r=mid;
else
l=mid;
}
return r;
}
vector<long long>subtask7(vector<int> X, vector<int> Y, vector<int> T, vector<int> B,vector<int> L, vector<int> R){
int n=X.size();
vector<bool>lin[3];
vector<bool>col[3];
int i;
for(i=0;i<3;++i){
lin[i].resize(n+5,0);
col[i].resize(n+5,0);
}
for(i=0;i<n;++i)
lin[0][i]=X[i];
for(i=0;i<n;++i)
col[0][i]=Y[i];
lin[1][0]=col[0][1];
lin[2][0]=col[0][2];
col[1][0]=lin[0][1];
col[2][0]=lin[0][2];
for(i=1;i<n;++i){
lin[1][i]=(!lin[1][i-1] && !lin[0][i])?1:0;
lin[2][i]=(!lin[2][i-1] && !lin[1][i])?1:0;
col[1][i]=(!col[1][i-1] && !col[0][i])?1:0;
col[2][i]=(!col[2][i-1] && !col[1][i])?1:0;
}
vector<int>diag;
for(i=n-1;i>2;--i)
if(col[2][i])
diag.push_back(get_diag(i,2,n));
for(i=2;i<n;++i)
if(lin[2][i])
diag.push_back(get_diag(2,i,n));
vector<int>splin[3];
vector<int>spcol[3];
int j;
for(i=0;i<3;++i){
splin[i].resize(n+5,0);
spcol[i].resize(n+5,0);
}
for(i=0;i<3;++i){
splin[i][0]=lin[i][0];
spcol[i][0]=col[i][0];
for(j=1;j<n;++j){
splin[i][j]=splin[i][j-1]+lin[i][j];
spcol[i][j]=spcol[i][j-1]+col[i][j];
}
}
int q=T.size();
vector<long long>answer;
diag.push_back(2e9);
for(i=0;i<q;++i){
int top=T[i];
int bottom=B[i];
int left=L[i];
int right=R[i];
if(top<3){
answer.push_back(splin[top][right]-splin[top][left-1]);
}
else{
int cnt=0;
if(left<=0 && 0<=right){
cnt+=col[0][top];
++left;
}
if(left<=1 && 1<=right){
cnt+=col[1][top];
++left;
}
if(left>right)
answer.push_back(cnt);
else{
int ind1=bin_search(diag,get_diag(top,left,n));
int ind2=bin_search(diag,get_diag(top,right,n)+1);
answer.push_back(ind2-ind1+cnt);
}
}
}
return answer;
}
long long spdst(int d1,int d2,vector<int>&cnt,vector<long long>&sum){
return sum[d2]-sum[d1-1]-1LL*cnt[d1-1]*(d2-d1+1);
}
long long spddr(int d1,int d2,vector<int>&cnt,vector<long long>&sum){
return sum[d1]-sum[d2+1]-1LL*cnt[d2+1]*(d2-d1+1);
}
long long get_answer(int top,int bottom,int left,int right,int n,vector<int>&cntst,vector<int>&cntdr,vector<long long>&sumst,vector<long long>&sumdr){
if(bottom-left>right-left){
int diag1=get_diag(top,left,n);
int diag2=get_diag(bottom,right,n);
int diag3=get_diag(top,right,n);
int diag4=get_diag(bottom,left,n);
return 1LL*(right-left+1)*(cntst[diag1]-cntst[diag2-1])+spdst(diag1+1,diag3,cntst,sumst)+spddr(diag4,diag2-1,cntdr,sumdr);
}
else{
int diag1=get_diag(top,left,n);
int diag2=get_diag(bottom,right,n);
int diag3=get_diag(top,right,n);
int diag4=get_diag(bottom,left,n);
return 1LL*(bottom-top+1)*(cntst[diag2]-cntst[diag1-1])+spdst(diag2+1,diag3,cntst,sumst)+spddr(diag4,diag1-1,cntdr,sumdr);
}
}
vector<long long>subtask8(vector<int> X, vector<int> Y, vector<int> T, vector<int> B,vector<int> L, vector<int> R){
int n=X.size();
vector<bool>lin[3];
vector<bool>col[3];
int i;
for(i=0;i<3;++i){
lin[i].resize(n+5,0);
col[i].resize(n+5,0);
}
for(i=0;i<n;++i)
lin[0][i]=X[i];
for(i=0;i<n;++i)
col[0][i]=Y[i];
lin[1][0]=col[0][1];
lin[2][0]=col[0][2];
col[1][0]=lin[0][1];
col[2][0]=lin[0][2];
for(i=1;i<n;++i){
lin[1][i]=(!lin[1][i-1] && !lin[0][i])?1:0;
lin[2][i]=(!lin[2][i-1] && !lin[1][i])?1:0;
col[1][i]=(!col[1][i-1] && !col[0][i])?1:0;
col[2][i]=(!col[2][i-1] && !col[1][i])?1:0;
}
vector<int>splin[3];
vector<int>spcol[3];
int j;
for(i=0;i<3;++i){
splin[i].resize(n+5,0);
spcol[i].resize(n+5,0);
}
for(i=0;i<3;++i){
splin[i][0]=lin[i][0];
spcol[i][0]=col[i][0];
for(j=1;j<n;++j){
splin[i][j]=splin[i][j-1]+lin[i][j];
spcol[i][j]=spcol[i][j-1]+col[i][j];
}
}
vector<bool>diag(2*n+5,0);
for(i=2;i<n;++i)
if(lin[2][i])
diag[get_diag(2,i,n)]=1;
for(i=2;i<n;++i)
if(col[2][i])
diag[get_diag(i,2,n)]=1;
vector<int>cntst(2*n+5,0);
vector<int>cntdr(2*n+5,0);
vector<long long>sumst(2*n+5,0);
vector<long long>sumdr(2*n+5,0);
for(i=0;i<2*n+5;++i){
cntst[i]=cntst[i-1]+diag[i];
sumst[i]=sumst[i-1]+cntst[i];
}
for(i=2*n+4;i>=0;--i){
cntdr[i]=cntdr[i+1]+diag[i];
sumdr[i]=sumdr[i+1]+cntdr[i];
}
int q=T.size();
vector<long long>answer;
for(i=0;i<q;++i){
int top=T[i];
int bottom=B[i];
int left=L[i];
int right=R[i];
int cnt=0;
if(top==0){
cnt+=splin[0][right]-((left)?splin[0][left-1]:0);
++top;
}
if(top>bottom){
answer.push_back(cnt);
continue;
}
if(top==1){
cnt+=splin[1][right]-((left)?splin[1][left-1]:0);
++top;
}
if(top>bottom){
answer.push_back(cnt);
continue;
}
if(left==0){
cnt+=spcol[0][bottom]-((top)?spcol[0][top-1]:0);
++left;
}
if(left>right){
answer.push_back(cnt);
continue;
}
if(left==1){
cnt+=spcol[1][bottom]-((top)?spcol[1][top-1]:0);
++left;
}
if(left>right){
answer.push_back(cnt);
continue;
}
answer.push_back(get_answer(top,bottom,left,right,n,cntst,cntdr,sumst,sumdr)+cnt);
}
return answer;
}
vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B,vector<int> L, vector<int> R){
return subtask8(X,Y,T,B,L,R);
}
