#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
vector<int> csum, rsum, cpsum, rpsum;
vector<vector<int> > srow, scol;
int sum(int h, int w){
if (h<=0||w<=0)return 0;
if (h>w)return csum[w]+rsum[h]-rsum[h-w]-csum[1]*min(h, w);
return csum[w]+rsum[h]-csum[w-h]-csum[1]*min(h, w);
}
int special(int t, int b, int l, int r){
if (t>2&&l>2)return 0;
if (b<=2)return srow[b][r]-(t?srow[t-1][r]:0)-(l?srow[b][l-1]:0)+(t&&l?srow[t-1][l-1]:0);
if (r<=2)return scol[b][r]-(l?scol[b][l-1]:0)-(t?scol[t-1][r]:0)+(t&&l?scol[t-1][l-1]:0);
if (t<=2&&l<=2)return srow[2][r]-(t?srow[t-1][r]:0)-(l?srow[2][l-1]:0)+(t&&l?srow[t-1][l-1]:0)+scol[b][2]-(l?scol[b][l-1]:0)-scol[2][2]+(l?scol[2][l-1]:0);
if (t<=2)return srow[min(b, 2ll)][r]-(t?srow[t-1][r]:0)-(l?srow[min(b, 2ll)][l-1]:0)+(t&&l?srow[t-1][l-1]:0);
if (l<=2)return scol[b][min(r, 2ll)]-(l?scol[b][l-1]:0)-(t?scol[t-1][min(r, 2ll)]:0)+(t&&l?scol[t-1][l-1]:0);
return 0;
}
vector<int> mosaic(vector<signed> x, vector<signed> y, vector<signed> t, vector<signed> b, vector<signed> l, vector<signed> r){
int n=x.size();
vector<vector<int> > row(3, vector<int>(n, 0)), col(n, vector<int>(3, 0));
srow.resize(3, vector<int>(n, 0));
scol.resize(n, vector<int>(3, 0));
for (int i=0; i<n; ++i)row[0][i]=srow[0][i]=x[i], col[i][0]=scol[i][0]=y[i];
for (int i=0; i<3; ++i)row[i][0]=srow[i][0]=y[i], col[0][i]=scol[0][i]=x[i];
for (int i=1; i<3; ++i)for (int j=1; j<n; ++j)if (!row[i-1][j]&&!row[i][j-1])srow[i][j]=row[i][j]=1;
for (int i=1; i<n; ++i)for (int j=1; j<3; ++j)if (!col[i-1][j]&&!col[i][j-1])scol[i][j]=col[i][j]=1;
for (int i=1; i<3; ++i)for (int j=0; j<n; ++j)srow[i][j]+=srow[i-1][j];
for (int i=0; i<3; ++i)for (int j=1; j<n; ++j)srow[i][j]+=srow[i][j-1];
for (int i=1; i<n; ++i)for (int j=0; j<3; ++j)scol[i][j]+=scol[i-1][j];
for (int i=0; i<n; ++i)for (int j=1; j<3; ++j)scol[i][j]+=scol[i][j-1];
rsum.resize(n-1, 0);
csum.resize(n-1, 0);
rpsum.resize(n-1, 0);
cpsum.resize(n-1, 0);
for (int i=1; i<n-1; ++i)rpsum[i]=rpsum[i-1]+row[2][i+1], cpsum[i]=cpsum[i-1]+col[i+1][2], csum[i]=csum[i-1]+cpsum[i], rsum[i]=rsum[i-1]+rpsum[i];
vector<int> ans(r.size());
for (int i=0; i<r.size(); ++i)ans[i]=special(t[i], b[i], l[i], r[i])+sum(b[i]-max(3, t[i])+1, r[i]-max(3, l[i])+1);
return ans;
}
