#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
struct cell
{
int i1,j1,i2,j2;
};
int n,q,a[200005],b[200005],c[200005],d[200005],mat[50][50];
vector<int>v[200005],br[200005],p[200005];
cell g[200005];
vector<long long int>otg;
void print()
{
for(int i=0;i<n;i++)
{
cout<<v[0][i]<<" ";
}
cout<<endl;
for(int i=0;i<n;i++)
{
cout<<v[1][i]<<" ";
}
cout<<endl;
for(int i=0;i<n;i++)
{
cout<<v[2][i]<<" ";
}
cout<<endl;
for(int i=3;i<n;i++)
{
for(int j=0;j<3;j++)
{
cout<<v[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
void fix_br(int i,int j)
{
if(j==0&&i<2)
{
br[i].push_back(v[i][j]);
return;
}
if(i==2&&j<=2)
{
br[i].push_back(v[i][j]);
return;
}
if(i<2||(i==2&&j>2))
{
br[i].push_back(br[i][j-1]+v[i][j]);
return;
}
if(i>2)
{
br[i].push_back(br[i-1][j]+v[i][j]);
return;
}
}
void fix_p(int i,int j)
{
if(j==0&&i<2)
{
p[i].push_back(0+i*br[i][j]);
}
if(i==2&&j<=2)
{
p[i].push_back(0+i*br[i][j]);
}
if(i<2||(i==2&&j>2))
{
p[i].push_back(p[i][j-1]+j*v[i][j]);
}
if(i>2)
{
p[i].push_back(p[i-1][j]+i*v[i][j]);
}
}
void dumb()
{
for(int i=1;i<n;i++)
{
for(int j=1;j<n;j++)
{
mat[i][j]=((mat[i-1][j]|mat[i][j-1])^1);
}
}
int br=0;
for(int z=1;z<=q;z++)
{
br=0;
for(int i=g[z].i1;i<=g[z].i2;i++)
{
for(int j=g[z].j1;j<=g[z].j2;j++)
{
br+=mat[i][j];
}
}
otg.push_back(br);
}
}
vector<long long> mosaic(vector<int> X,vector<int> Y,vector<int> T,vector<int> B,vector<int> L,vector<int> R)
{
n=X.size();
q=T.size();
for(int i=0;i<q;i++)
{
g[i+1].i1=T[i];
g[i+1].i2=B[i];
g[i+1].j1=L[i];
g[i+1].j2=R[i];
}
if(n<=2)
{
for(int i=0;i<n;i++)
{
mat[0][i]=X[i];
}
for(int i=0;i<n;i++)
{
mat[i][0]=Y[i];
}
dumb();
return otg;
}
for(int i=0;i<n;i++)
{
v[0].push_back(X[i]);
if(i)
{
v[i].push_back(Y[i]);
}
}
for(int i=1;i<n;i++)
{
v[1].push_back((v[1][i-1]|v[0][i])^1);
if(i!=1)v[i].push_back((v[i-1][1]|v[i][0])^1);
}
for(int i=2;i<n;i++)
{
v[2].push_back((v[2][i-1]|v[1][i])^1);
if(i!=2)
{
v[i].push_back((v[i-1][2]|v[i][1])^1);
}
}
int sz;
for(int i=0;i<n;i++)
{
sz=n;
if(i>2)sz=3;
for(int j=0;j<sz;j++)
{
fix_br(i,j);
fix_p(i,j);
}
}
long long int ot=0;
//print();
for(int z=1;z<=q;z++)
{
ot=0;
for(int i=g[z].i1;i<min(g[z].i2+1,2);i++)
{
ot+=br[i][g[z].j2];
if(g[z].j1)ot-=br[i][g[z].j1-1];
}
if(g[z].i2>1)
{
for(int j=g[z].j1;j<min(g[z].j2+1,2);j++)
{
ot+=br[g[z].i2][j];
if(g[z].i1>2)ot-=br[g[z].i1-1][j];
}
}
g[z].i1=max(g[z].i1,2);
g[z].j1=max(g[z].j1,2);
g[z].i2-=(g[z].j1-2);
g[z].j2-=(g[z].i1-2);
//cout<<g[z].i2<<" "<<g[z].j2<<endl;
//cout<<p1[g[z].j2]<<" "<<p2[g[z].i2]<<endl;
//cout<<br1[g[z].j2]<<" "<<br2[g[z].i2]<<endl;
if(g[z].j2>=2)
{
ot+=(br[2][g[z].j2]*(g[z].j2+1))-p[2][g[z].j2];
}
if(g[z].i2>=3)
{
ot+=(br[g[z].i2][2]*(g[z].i2+1))-p[g[z].i2][2];
}
otg.push_back(ot);
}
return otg;
}
