#include <bits/stdc++.h>
using namespace std;
#include "mosaic.h"
#define pb push_back
const int pls=4e5,N=1e6+5;
int pref[N],prefx[pls][2],prefy[pls][2];
vector<long long> mosaic(vector<int> X, vector<int> Y,vector<int> T, vector<int> B,vector<int> L, vector<int> R) {
int n=X.size();
int a[3][n];
for(int i=0;i<N;i++)pref[i]=0;
for(int i=0;i<X.size();i++){
a[0][i]=X[i];
prefx[i][0]=X[i];
if(i>0)prefx[i][0]+=prefx[i-1][0];
}
for(int i=1;i<3;i++){
a[i][0]=Y[i];
if(i==1)prefx[0][i]=Y[i];
for(int j=1;j<n;j++){
if(a[i][j-1]==0 && a[i-1][j]==0){
a[i][j]=1;
if(i==2 && j>1)pref[i-j+pls]=1;
}
else a[i][j]=0;
if(i==1)prefx[j][i]=a[i][j]+prefx[j-1][i];
}
}
int b[n][3];
for(int i=0;i<Y.size();i++){
b[i][0]=Y[i];
prefy[i][0]=Y[i];
if(i>0)prefy[i][0]+=prefy[i-1][0];
}
for(int i=1;i<3;i++){
b[0][i]=X[i];
if(i==1)prefy[0][i]=Y[i];
for(int j=1;j<n;j++){
if(b[j][i-1]==0 && b[j-1][i]==0){
b[j][i]=1;
if(i==2 && j>1){
// cout<<j<<' '<<i<<' '<<j-i+pls<<endl;
pref[j-i+pls]=1;
}
}
else b[j][i]=0;
if(i==1)prefy[j][i]=b[j][i]+prefy[j-1][i];
}
}
for(int i=1;i<N;i++)pref[i]+=pref[i-1];
vector<long long> ans;
for(int i=0;i<T.size();i++){
long long sum=0;
while(T[i]<2 && T[i]<=B[i]){
sum+=prefx[R[i]][T[i]]-(L[i]>0?prefx[L[i]-1][T[i]]:0);
T[i]++;
}
if(T[i]>B[i]){
ans.pb(sum);
continue;
}
while(L[i]<2 && L[i]<=R[i]){
sum+=prefy[B[i]][L[i]]-prefy[T[i]-1][L[i]];
L[i]++;
}
if(L[i]>R[i]){
ans.pb(sum);
continue;
}
int pos2=T[i]-L[i]+pls,pos1=T[i]-R[i]+pls;
// cout<<L[i]<<' '<<R[i]<<' '<<pref[pos2]<<' '<<pref[pos1-1]<<' '<<pos2<<endl;
ans.pb(pref[pos2]-pref[pos1-1]+sum);
}
return ans;
}
/*
* 4
1 0 1 0
1 1 0 1
1
2 2 0 3
*/
