#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<long long>> a,a2;
vector<long long> p1,p2;
long long calc(int x,int y){
if(x<=3||y<=3)return a2[x][y];
long long p=a2[2][y]+a2[x][2]-a2[2][2];
x-=2;
y-=2;
if(x<=y)return p+p1[y]+p2[x]-p1[y-x]-a[3][3]*x;
return p+p1[y]+p2[x]-p2[x-y]-a[3][3]*y;
}
std::vector<long long> mosaic(std::vector<int> x, std::vector<int> y,
std::vector<int> t, std::vector<int> b,
std::vector<int> l, std::vector<int> r) {
int n=x.size();
a.resize(n+1);
a2.resize(n+1);
a[0].resize(n+1);
a2[0].resize(n+1);
for(int i=1;i<=n;i++){
a[i].push_back(0);
a2[i].push_back(0);
for(int j=1;j<=n&&(i<=3||j<=3);j++){
if(i==1)a[i].push_back(x[j-1]);
else if(j==1)a[i].push_back(y[i-1]);
else{
a[i].push_back(!a[i-1][j]&&!a[i][j-1]);
}
a2[i].push_back(a[i][j]-a2[i-1][j-1]+a2[i-1][j]+a2[i][j-1]);
}
}
if(n>=3){
p1.resize(n-1);
for(int i=1;i<=n-2;i++)p1[i]=a[3][i+2];
for(int i=1;i<=n-2;i++)p1[i]+=p1[i-1];
for(int i=1;i<=n-2;i++)p1[i]+=p1[i-1];
p2.resize(n-1);
for(int i=1;i<=n-2;i++)p2[i]=a[i+2][3];
for(int i=1;i<=n-2;i++)p2[i]+=p2[i-1];
for(int i=1;i<=n-2;i++)p2[i]+=p2[i-1];
}
int q=t.size();
vector<long long> ans(q);
for(int i=0;i<q;i++){
r[i]++;
b[i]++;
ans[i]=calc(b[i],r[i])+calc(t[i],l[i])-calc(t[i],r[i])-calc(b[i],l[i]);
}
return ans;
}
