#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> mosaic(vector<signed> X, vector<signed> Y, vector<signed> t, vector<signed> b, vector<signed> l, vector<signed> r){
if (X.size()<=10){
int n=X.size();
vector<int> ans(r.size());
vector<vector<int> > grid(n, vector<int>(n, 0));
for (int i=0; i<n; ++i)grid[0][i]=X[i], grid[i][0]=Y[i];
for (int i=1; i<n; ++i)for (int j=1; j<n; ++j)if (!grid[i-1][j]&&!grid[i][j-1])grid[i][j]=1;
for (int i=1; i<n; ++i)for (int j=0; j<n; ++j)grid[i][j]+=grid[i-1][j];
for (int i=1; i<n; ++i)for (int j=0; j<n; ++j)grid[j][i]+=grid[j][i-1];
for (int i=0; i<r.size(); ++i)ans[i]=grid[b[i]][r[i]]-(t[i]?grid[t[i]-1][r[i]]:0)-(l[i]?grid[b[i]][l[i]-1]:0)+(t[i]&&l[i]?grid[t[i]-1][l[i]-1]:0);
return ans;
}
int n=X.size();
vector<int> ans(r.size());
vector<vector<int> > grid(n, vector<int>(n, 0));
for (int i=0; i<n; ++i)grid[0][i]=X[i], grid[i][0]=Y[i];
for (int i=1; i<5; ++i)for (int j=1; j<n; ++j)if (!grid[i-1][j]&&!grid[i][j-1])grid[i][j]=1;
for (int i=5; i<n; ++i){
for (int j=1; j<n; ++j)grid[i][j]=grid[i-1][j-1];
if (grid[i][0])grid[i][1]=0;
if (!grid[i][1]&&!grid[i][2]&&!grid[i][3])grid[i][2]=1;
}
for (int i=1; i<n; ++i)for (int j=0; j<n; ++j)grid[i][j]+=grid[i-1][j];
for (int i=1; i<n; ++i)for (int j=0; j<n; ++j)grid[j][i]+=grid[j][i-1];
for (int i=0; i<r.size(); ++i)ans[i]=grid[b[i]][r[i]]-(t[i]?grid[t[i]-1][r[i]]:0)-(l[i]?grid[b[i]][l[i]-1]:0)+(t[i]&&l[i]?grid[t[i]-1][l[i]-1]:0);
return ans;
}
