#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[5050][5050];
ll n;
void update(ll i, ll j, ll val){
for(i; i <= n; i += i&-i) for(ll k = j; k <= n; k += k&-k) f[i][k] += val;
}
ll query(ll i, ll j){
ll sum = 0;
for(i; i > 0; i -= i&-i) for(ll k = j; k > 0; k -= k&-k) sum += f[i][k];
return sum;
}
ll sum(ll a, ll b, ll c, ll d){
return query(c, d) - query(a-1, d) - query(c, b-1) + query(a-1, b-1);
}
vector<long long> mosaic(vector<int> x, vector<int> y, vector<int> t, vector<int> b, vector<int> l, vector<int> r) {
n = x.size();
vector<vector<ll>> v(n+1, vector<ll>(n+1));
for(ll i = 0; i < n; i++) v[1][i+1] = x[i];
for(ll j = 0; j < n; j++) v[j+1][1] = y[j];
for(ll i = 2; i <= n; i++) for(ll j = 2; j <= n; j++) v[i][j] = (!v[i][j-1] && !v[i-1][j]);
for(ll i = 1; i <= n; i++) for(ll j = 1; j <= n; j++) update(i, j, v[i][j]);
ll q = t.size();
vector<ll> ans(q);
for(ll i = 0; i < q; i++) ans[i] = sum(t[i]+1, l[i]+1, b[i]+1, r[i]+1);
return ans;
}
