#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
vector<long long> mosaic(vector<int> a, vector<int> b,vector<int> r,
vector<int> r1,vector<int> c, vector<int> c1)
{
int n=a.size();
vector<int> rw[3],cl[3];
vector<ll> v;
set<pair<int,int>> se;
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
{
if (i>3 && j>3) break;
if (!i)
{
if (a[j]) se.insert({i,j}),rw[0].push_back(j);
}
else if (!j)
{
if (b[i])
{
se.insert({i,j}),cl[0].push_back(i);
if (i<3) rw[i].push_back(j);
}
}
else
{
if (!se.count({i-1,j}) && !se.count({i,j-1}))
{
se.insert({i,j});
if (min(i,j)==3)
v.push_back(i-j);
else
{
if (i<3) rw[i].push_back(j);
else if (j<3) cl[j].push_back(i);
}
}
}
}
for (int i=0;i<3;i++)
sort(all(rw[i])),sort(all(cl[i]));
sort(all(v));
int m=v.size();
ll pre[m]={};
for (int i=1;i<=m;i++)
pre[i]=pre[i-1]+v[i-1];
vector<ll> ans(r.size());
for (int i=0;i<(int)r.size();i++)
{
for (int j=0;j<3;j++)
{
if (j>=r[i] && j<=r1[i])
ans[i]+=upper_bound(all(rw[j]),c1[i])-lower_bound(all(rw[j]),c[i]);
if (j>=c[i] && j<=c1[i] && r1[i]>2)
ans[i]+=upper_bound(all(cl[j]),r1[i])-lower_bound(all(cl[j]),max(3,r[i]));
}
r[i]=max(r[i],3);
c[i]=max(c[i],3);
if (r[i]>r1[i] or c[i]>c1[i]) continue;
if (lower_bound(all(v),r[i]-c[i])!=upper_bound(all(v),r1[i]-c[i]))
{
int x=lower_bound(all(v),r[i]-c[i])-begin(v);
int y=upper_bound(all(v),r1[i]-c[i])-begin(v)-1;
int s=x-1,e=y+1;
while (s+1<e)
{
int mid=(s+e)/2;
if (r1[i]-(v[mid]+c[i])>=c1[i]-c[i])
s=mid;
else
e=mid;
}
ans[i]+=1ll*(c1[i]-c[i]+1)*(s-x+1);
ll su=pre[y+1]-pre[s+1]+1ll*c[i]*(y-s);
ans[i]+=1ll*(r1[i]+1)*(y-s)-su;
}
if (c[i]==c1[i]) continue;
c[i]++;
if (lower_bound(all(v),r[i]-c1[i])!=upper_bound(all(v),r[i]-c[i]))
{
int x=lower_bound(all(v),r[i]-c1[i])-begin(v);
int y=upper_bound(all(v),r[i]-c[i])-begin(v)-1;
int s=x-1,e=y+1;
while (s+1<e)
{
int mid=(s+e)/2;
if (c1[i]-(r[i]-v[mid])>=r1[i]-r[i])
e=mid;
else
s=mid;
}
ans[i]+=1ll*(r1[i]-r[i]+1)*(y-e+1);
ll su=1ll*r[i]*(e-x)-(pre[e]-pre[x]);
ans[i]+=1ll*(c1[i]+1)*(e-x)-su;
}
}
return ans;
}
