#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],br1[200005],br2[200005],p1[200005],p2[200005];
vector<int>v[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 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);
p1[i]=p1[i-1];
br1[i]=br1[i-1];
if(v[2][i])
{
p1[i]+=i;
br1[i]++;
}
if(i!=2)
{
v[i].push_back((v[i-1][2]|v[i][1])^1);
p2[i]=p2[i-1];
br2[i]=br2[i-1];
if(v[i][2])
{
p2[i]+=i;
br2[i]++;
}
}
}
long long int br=0;
int sz;
//print();
for(int z=1;z<=q;z++)
{
br=0;
for(int i=g[z].i1;i<g[z].i2+1;i++)
{
sz=v[i].size();
if(i>1)sz=2;
for(int j=g[z].j1;j<min(sz,g[z].j2+1);j++)
{
br+=v[i][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)
{
br+=(br1[g[z].j2]*(g[z].j2+1))-p1[g[z].j2];
}
if(g[z].i2>=3)
{
br+=(br2[g[z].i2]*(g[z].i2+1))-p2[g[z].i2];
}
otg.push_back(br);
}
return otg;
}
