#include "mosaic.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pii pair <ll, ll>
#define el '\n'
#define fr(i, l, r) for(ll (i) = l; (i) <= r; (i)++)
#define frb(i, r, l) for(ll (i) = r; (i) >= l; (i)--)
ll const N = 5e3 + 100;
ll pref[N][N];
ll f(ll a, ll b) {
if(a < 0 || b < 0)
return 0;
return pref[a][b];
}
std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> L, std::vector<int> R) {
int Q = (int)T.size();
int N = (int)X.size();
fr(i, 0, N - 1)
pref[0][i] = X[i];
fr(i, 0, N - 1)
pref[i][0] = Y[i];
fr(i, 1, N - 1) {
fr(j, 1, N - 1) {
ll val = pref[i - 1][j] | pref[i][j - 1];
val ^= 1;
pref[i][j] = val;
}
}
fr(i, 0, N - 1) {
fr(j, 0, N - 1) {
if(i)
pref[i][j] += pref[i - 1][j];
if(j)
pref[i][j] += pref[i][j - 1];
if(i && j)
pref[i][j] -= pref[i - 1][j - 1];
}
}
vector <ll> ans(Q);
fr(i, 0, Q - 1) {
ans[i] += f(B[i], R[i]);
ans[i] -= f(T[i] - 1, R[i]);
ans[i] -= f(B[i], L[i] - 1);
ans[i] += f(T[i] - 1, L[i] - 1);
}
return ans;
}
