#include "mosaic.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
vi mosaic(vector<signed> X,vector<signed> Y,vector<signed> T,vector<signed> B,vector<signed> L,vector<signed> R) {
int n=size(X),q=size(T);
vi C(q);
vvi v(max(n,(int)3),vi(3,0)); //this vector contains the values of only the first three layers of the binary grid
if(n>=3){
for(int i=0;i<3;i++)v[i].resize(n,0);
} //the first three rows each contain n elements which belong to the first three layers so we have to extend the vector for these rows
for(int i=0;i<n;i++) v[0][i]=X[i];
for(int i=0;i<n;i++) v[i][0]=Y[i];
//initialise the values in the first layer
for(int i=1;i<n;i++){
if(v[0][i]==1 || v[1][i-1]==1) v[1][i]=0;
else v[1][i]=1;
if(v[1][i]==1 || v[2][i-1]==1) v[2][i]=0;
else v[2][i]=1;
//then we fill in the next two rows by following using the previous row
}
for(int i=1;i<n;i++){
if(v[i][0]==1 || v[i-1][1]==1) v[i][1]=0;
else v[i][1]=1;
if(v[i][1]==1 || v[i-1][2]==1) v[i][2]=0;
else v[i][2]=1;
//then we fill in the next two columns by following using the previous column
}
vvi pref(6,vi(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];
//row sums
pref[3+j][i+1]=pref[3+j][i]+v[i][j];
//column sums
}
}
map<int,int>pref1,pref2;
//prefix sums of the first two layers
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++){
C[i]=0;
int x1=T[i],x2=B[i],y1=L[i],y2=R[i];
while(x1<2){
if(x1>x2) break;
C[i]+=(pref[x1][y2+1]-pref[x1][y1]);
x1++;
}
//we keep incrementing row-wise as we go along the layers till we reach layer 2 (as we precompute the answers for layers 0 and 1 so we only need to consider the subgrid that lies in layers 2 and above)
if(x1>x2) continue;
while(y1<2){
if(y1>y2)break;
C[i]+=(pref[3+y1][x2+1]-pref[3+y1][x1]);
y1++;
}
//again incremementing till we're in layer 2, this time column-wise
if(y1>y2) continue;
int d1=x2-x1+1,d2=y2-y1+1;
int num=y2-x1;
C[i]+=pref2[num]-pref2[num-d1]-pref2[num-d2]+pref2[num-d1-d2];
//then we look at how the subgrid/rectangle maps to layer 2 - the number of occurences of each element of layer 2 in the subrectangle - and we compute what this gives based off of the precomputed values of the prefix sums
}
return C;
}
