#include "mosaic.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back
typedef long long ll;
namespace{
const ll mxN=5005;
ll n, q;
ll a[mxN][mxN];
ll pre1[4][mxN], pre2[mxN][4];
ll val[2*mxN];
ll pre[2*mxN], pref[2*mxN], pres[2*mxN];
ll id(ll tar){
return tar+n-3;
}
}
vector<long long> mosaic(vector<int> X, vector<int> Y,
vector<int> T, vector<int> B,
vector<int> L, vector<int> R) {
memset(pre1, 0, sizeof(pre1));
memset(pre2, 0, sizeof(pre2));
n=X.size();
q=T.size();
for(ll i=0;i<n;i++){
a[0][i]=X[i];
// pre1[0][i]=a[0][i];
}
for(ll i=0;i<n;i++){
a[i][0]=Y[i];
// pre2[i][0]=b[i][0];
}
if(n<=2){
for(ll i=1;i<n;i++){
for(ll j=1;j<n;j++){
if(a[i-1][j]==0 && a[i][j-1]==0) a[i][j]=1;
else a[i][j]=0;
}
}
vll ans(q);
for(ll i=0;i<q;i++){
for(ll j=T[i];j<=B[i];j++){
for(ll k=L[i];k<=R[i];k++){
ans[i]+=a[j][k];
}
}
}
return ans;
}
for(ll i=1;i<n;i++){
for(ll j=1;j<n;j++){
if(a[i-1][j]==0 && a[i][j-1]==0) a[i][j]=1;
else a[i][j]=0;
}
}
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
pre1[i+1][j+1]=pre1[i][j+1]+pre1[i+1][j]-pre1[i][j]+a[i][j];
}
}
vll ans(q);
for(ll i=0;i<q;i++){
ans[i]=pre1[B[i]+1][R[i]+1]-pre1[T[i]][R[i]+1]-
pre1[B[i]+1][L[i]]+pre1[T[i]][L[i]];
}
return ans;
}
