#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];
vector<int>bb,pp;
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)
{
br[i].push_back(br[i][j-1]+v[i][j]);
return;
}
if(i>2&&j<2)
{
br[i].push_back(br[i-1][j]+v[i][j]);
return;
}
}
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);
}
}
void dob(long long int&ot,int ind,int sz,int mi)
{
ot+=(pp[ind+mi-1]-pp[ind-1])-((ind-1)*(bb[ind+mi-1]-bb[ind-1]));
ind+=mi;
sz-=mi;
if(sz>mi)
{
int lef=sz-mi;
ot+=(bb[ind+lef-1]-bb[ind-1])*mi;
sz-=lef;
ind+=lef;
}
if(sz)
{
ot+=(ind+sz)*(bb[ind+sz-1]-bb[ind-1])-(pp[ind+sz-1]-pp[ind-1]);
}
}
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>1)sz=2;
for(int j=0;j<sz;j++)
{
fix_br(i,j);
}
}
int last=0,lastp=0,cur=1;
bb.push_back(0);
pp.push_back(0);
for(int i=n-1;i>=2;i--)
{
bb.push_back(v[2][i]+last);
pp.push_back(v[2][i]*cur+lastp);
last=bb.back();
lastp=pp.back();
cur++;
}
for(int i=3;i<n;i++)
{
bb.push_back(v[i][2]+last);
pp.push_back(v[i][2]*cur+lastp);
last=bb.back();
lastp=pp.back();
cur++;
}
long long int ot=0;
int st;
//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);
if(g[z].i1>g[z].i2||g[z].j1>g[z].j2)
{
otg.push_back(ot);
continue;
}
st=g[z].j2-g[z].j1+1+g[z].i2-g[z].i1;
//cout<<g[z].i1<<" "<<g[z].i2<<" "<<g[z].j1<<" "<<g[z].j2<<endl;
if(g[z].i1<=g[z].j2)
{
//cout<<n-(g[z].j2-(g[z].i1-2))<<endl;
dob(ot,n-(g[z].j2-(g[z].i1-2)),st,min(g[z].j2-g[z].j1+1,g[z].i2-g[z].i1+1));
}
else
{
dob(ot,n-2+g[z].i1-(g[z].j2-2)-2,st,min(g[z].j2-g[z].j1+1,g[z].i2-g[z].i1+1));
}
otg.push_back(ot);
}
return otg;
}
