#include "mosaic.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#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);
if (n==1) {
vi C(q,X[0]);
return C;
} else if (n==2) {
int grid[2][2];
grid[0][0]=X[0]; grid[0][1]=X[1];
grid[1][0]=Y[1]; grid[1][1]=(1-X[1])&(1-Y[1]);
vi C(q);
for (int k=0;k<q;k++) {
C[k]=0;
int a=T[k],b=B[k],c=L[k],d=R[k];
for (int i=a;i<=b;i++) {
for (int j=c;j<=d;j++) C[k]+=grid[i][j];
}
}
return C;
}
vi layer0,layer1,layer2;
for (int i=n-1;i>0;i--) layer0.pb(Y[i]);
for (int i=0;i<n;i++) layer0.pb(X[i]);
vector<signed> X1,Y1;
X1.pb(Y[1]);
for (int i=1;i<n;i++) X1.pb((1-X[i])&(1-X1[i-1]));
Y1.pb(X[1]);
for (int i=1;i<n;i++) Y1.pb((1-Y[i])&(1-Y1[i-1]));
for (int i=n-1;i>1;i--) layer1.pb(Y1[i]);
for (int i=1;i<n;i++) layer1.pb(X1[i]);
vector<signed> X2,Y2;
X2.pb(Y1[2]);
for (int i=2;i<n;i++) X2.pb((1-X1[i])&(1-X2[i-2]));
Y2.pb(X1[2]);
for (int i=2;i<n;i++) Y2.pb((1-Y1[i])&(1-Y2[i-2]));
for (int i=n-2;i>1;i--) layer2.pb(Y2[i]);
for (int i=1;i<n-1;i++) layer2.pb(X2[i]);
/*
for (auto x:layer0) cout<<x<<" ";
cout<<endl;
for (auto x:layer1) cout<<x<<" ";
cout<<endl;
for (auto x:layer2) cout<<x<<" ";
cout<<endl;
*/
vi pre0(2*n),pre1(2*n-2);
pre0[0]=0; pre1[0]=0;
for (int i=0;i<2*n-1;i++) pre0[i+1]=pre0[i]+layer0[i];
for (int i=0;i<2*n-3;i++) pre1[i+1]=pre1[i]+layer1[i];
vi C(q);
for (int k=0;k<q;k++) {
C[k]=0;
int a=T[k],b=B[k],c=L[k],d=R[k];
if (a==0 || c==0) {
int x0,y0;
if (a>0) {
x0=n-b; y0=n-a;
} else if (c>0) {
x0=n+c; y0=n+d;
} else {
x0=n-b; y0=n+d;
}
//cout<<x0<<" "<<y0<<endl;
C[k]+=pre0[y0]-pre0[x0-1];
//cout<<C[k]<<endl;
}
if ((a<=1 && b>=1) || (c<=1 && d>=1)) {
int x1,y1;
if (a>1) {
x1=n-b; y1=n-a;
} else if (c>1) {
x1=n+c-2; y1=n+d-2;
} else {
x1=n-b; y1=n+d-2;
}
//cout<<x1<<" "<<y1<<endl;
C[k]+=pre1[y1]-pre1[x1-1];
//cout<<C[k]<<endl;
}
if (b>=2 && d>=2) {
a=max(a,(int)2); c=max(c,(int)2);
int xad=a-min(a-2,d-2),yad=d-min(a-2,d-2),xbc=b-min(b-2,c-2),ybc=c-min(b-2,c-2);
//cout<<xad<<" "<<yad<<" "<<xbc<<" "<<ybc<<endl;
int xx,yy;
if (xad==2) xx=n+yad-5;
else xx=n-xad-1;
if (xbc==2) yy=n+ybc-5;
else yy=n-xbc-1;
if (xx>yy) swap(xx,yy);
int l=yy-xx+1;
//cout<<xx<<" "<<yy<<endl;
for (int i=xx;i<=yy;i++) {
C[k]+=min(i-xx+1,yy-i+1)*layer2[i];
//cout<<min(i-xx+1,yy-i+1)<<endl;
}
//cout<<C[k]<<endl;
}
//cout<<C[k]<<endl;
}
return C;
//O(n*q) solution
}
