#include "mosaic.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> mosaic(vector<signed> X, vector<signed> Y,vector<signed> T, vector<signed> B,vector<signed> L, vector<signed> R) {
int Q = (int)T.size();
vector<int> C(Q);
int n=X.size();
vector<vector<int>>v(max(3LL,n),vector<int>(3,0));
if(n>=3){
for(int i=0;i<3;i++)v[i].resize(n,0);
}
for(int i=0;i<n;i++)v[0][i]=X[i];
for(int i=0;i<n;i++)v[i][0]=Y[i];
for(int i=1;i<n;i++){
if(v[0][i]==1LL||v[1][i-1]==1LL){
v[1][i]=0;
}else v[1][i]=1;
if(v[1][i]==1LL||v[2][i-1]==1LL){
v[2][i]=0;
}else v[2][i]=1;
}
for(int i=1;i<n;i++){
if(v[i][0]==1LL||v[i-1][1]==1LL){
v[i][1]=0;
}else v[i][1]=1;
if(v[i][1]==1LL||v[i-1][2]==1LL){
v[i][2]=0;
}else v[i][2]=1;
}
vector<vector<int>>pref(6,vector<int>(n+1,0));
for(int i=0;i<n;i++){
for(int j=0;j<3;j++){
pref[j][i+1]=pref[j][i]+v[j][i];
pref[3+j][i+1]=pref[3+j][i]+v[i][j];
}
}
map<int,int>pref1;
map<int,int>pref2;
if(n>=3){
for(int i=0;i<n;i++){
pref1[i]=0;
pref1[-i]=0;
pref2[i]=0;
pref2[-i]=0;
}
for(int i=n-1;i>=2;i--){
pref1[2-i]=pref1[1-i]+v[i][2];
}
for(int i=3;i<n;i++){
pref1[i-2]=pref1[i-3]+v[2][i];
}
pref2[-(n-3)]=pref1[-(n-3)];
for(int i=-(n-3);i<=(n-3);i++){
pref2[i]=pref2[i-1]+pref1[i];
}
}
for(int i=0;i<Q;i++){
int modif=0;
int x1=T[i];
int x2=B[i];
int y1=L[i];
int y2=R[i];
while(x1<2){
if(x1>x2)break;
modif+=(pref[x1][y2+1]-pref[x1][y1]);
x1++;
}
if(x1>x2){
C[i]=modif;
continue;
}
while(y1<2){
if(y1>y2)break;
modif+=(pref[3+y1][x2+1]-pref[3+y1][x1]);
y1++;
}
if(y1>y2){
C[i]=modif;
continue;
}
int d1=x2-x1+1;
int d2=y2-y1+1;
int num=y2-x1;
int sol=pref2[num]-pref2[num-d1]-pref2[num-d2]+pref2[num-d1-d2];
C[i]=modif+sol;
}
return C;
}
