#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++) {
if(t[i] == 0){
if(b[i] == 0) continue;
t[i] = 1;
}
if(l[i] == 0){
if(r[i] == 0) continue;
l[i] = 1;
}
ll h = b[i] - t[i] + 1, w = r[i] - l[i] + 1;
if((t[i] + l[i]) % 2 == 0) ans[i] = ((w + 1) / 2) * ((h + 1) / 2) + (w / 2) * (h / 2);
else ans[i] = ((w + 1) / 2) * (h / 2) + (w / 2) * ((h + 1) / 2);
}
return ans;
}
