#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> build_prefix_sum(const vector<vector<int>>& v){
int n=v.size();
vector<vector<int>> p(n+1,vector<int>(n+1));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
p[i][j]=v[i-1][j-1]+p[i-1][j]+p[i][j-1]-p[i-1][j-1];
}
}
return p;
}
int query(const vector<vector<int>>& p,int t,int b,int l,int r){
t++,b++,l++,r++;
return p[b][r]-p[t-1][r]-p[b][l-1]+p[t-1][l-1];
}
vector<long long> mosaic(vector<int> x,vector<int> y,vector<int> t,vector<int> b,vector<int> l,vector<int> r){
bool ok=true;
for(int i=0;i<t.size();i++){
if(t[i]!=0 || b[i]!=0){
ok=false;
}
}
if(ok){
vector<int> Px;
Px.push_back(0);
for(int i=0;i<x.size();i++){
Px.push_back(Px[i]+x[i]);
}
vector<long long> ans;
for(int i=0;i<t.size();i++){
ans.push_back(Px[r[i]+1]-Px[l[i]]);
}
return ans;
}
int n=x.size();
vector<vector<int>> v(n,vector<int>(n));
for(int i=0;i<n;i++)v[0][i]=x[i];
for(int i=0;i<n;i++)v[i][0]=y[i];
for(int i=1;i<n;i++){
for(int j=1;j<n;j++){
v[i][j]=(v[i-1][j]==0 && v[i][j-1]==0);
}
}
vector<vector<int>> p=build_prefix_sum(v);
vector<long long> ans;
for(int i=0;i<t.size();i++)ans.push_back(query(p,t[i],b[i],l[i],r[i]));
return ans;
}
