#include <bits/stdc++.h>
#include "mosaic.h"
using namespace std;
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 m=T.size();
vector<long long>res;
if(n<3)
{
int v[n][n];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==0)v[i][j]=X[i];
else if(j==0)v[i][j]=Y[i];
else v[i][j]=((v[i-1][j]|v[i][j-1])+1)%2;
}
}
for(int k=0;k<m;k++)
{
int sum=0;
for(int i=T[k];i<=B[k];i++)
{
for(int j=L[k];j<=R[k];j++)sum+=v[i][j];
}
res.push_back(sum);
}
return res;
}
else
{
long long x1[3][n],y1[n][3],prefx[3][n+1],prefy[n+1][3];
for(int i=0;i<3;i++)
{
prefx[i][0]=0;
for(int j=0;j<n;j++)
{
if(i==0)x1[i][j]=X[j];
else if(j==0)x1[i][j]=Y[i];
else x1[i][j]=((x1[i][j-1]|x1[i-1][j])+1)%2;
prefx[i][j+1]=prefx[i][j]+x1[i][j];
}
}
for(int j=0;j<3;j++)
{
prefy[0][j]=0;
for(int i=0;i<n;i++)
{
if(i==0)y1[i][j]=X[j];
else if(j==0)y1[i][j]=Y[i];
else y1[i][j]=((y1[i][j-1]|y1[i-1][j])+1)%2;
prefy[i+1][j]=prefy[i][j]+y1[i][j];
}
}
vector<long long>v(2*n),pv(2*n+1),sv(2*n+1),p1(2*n+1),s1(2*n+1);
for(int i=2;i<n;i++)
{
v[n+i-2]=x1[2][i];
v[n+2-i]=y1[i][2];
}
pv[0]=0;p1[0]=0;s1[2*n]=0;sv[2*n]=0;
long long k=1;
for(int i=0;i<2*n;i++)
{
pv[i+1]=pv[i]+k*v[i];k++;
p1[i+1]=p1[i]+v[i];
}
k=1;
for(int i=2*n-1;i>=0;i--)
{
sv[i]=sv[i+1]+k*v[i];k++;
s1[i]=s1[i+1]+v[i];
}
for(int i=0;i<m;i++)
{
long long sum=0;
if(B[i]<=1)
{
for(int j=T[i];j<=B[i];j++)
{
sum+=prefx[j][R[i]+1]-prefx[j][L[i]];
}
res.push_back(sum);continue;
}
if(R[i]<=1)
{
for(int j=L[i];j<=R[i];j++)
{
sum+=prefy[B[i]+1][j]-prefy[T[i]][j];
}
res.push_back(sum);continue;
}
if(T[i]<=1)
{
for(int j=T[i];j<2;j++)
{
sum+=prefx[j][R[i]+1]-prefx[j][L[i]];
}
T[i]=2;
}
if(L[i]<=1)
{
for(int j=L[i];j<2;j++)
{
sum+=prefy[B[i]+1][j]-prefy[T[i]][j];
}
L[i]=2;
}
cout<<sum<<" ";
vector<long long>temp={n+L[i]-B[i],n+L[i]-T[i],n+R[i]-B[i],n+R[i]-T[i]};
sort(temp.begin(),temp.end());
long long a=temp[0],b=temp[1],c=temp[2],d=temp[3];
cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
sum+=pv[b]-pv[a]-(p1[b]-p1[a])*(a);
sum+=(p1[c+1]-p1[b])*(b-a+1ll);
sum+=(sv[c]-sv[d])-(s1[c]-s1[d])*(2*n-d-1);
res.push_back(sum);
}
return res;
}
}
