#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, q;
vector<int> x, y, a, b, l, r;
vector<ll> solve3() {
for (int i = 1; i < n; i++) x[i] += x[i-1];
vector<ll> fin;
for (int i = 0; i < q; i++) {
ll ans = x[r[i]];
if (l[i] > 0) ans -= x[l[i] - 1];
fin.push_back(ans);
}
return fin;
}
vector<ll> solve124() {
vector<vector<ll>> grid(n, vector<ll>(n, 0));
for (int i = 0; i < n; i++) grid[0][i] = x[i];
for (int i = 0; i < n; i++) grid[i][0] = y[i];
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
if (grid[i-1][j] || grid[i][j-1]) grid[i][j] = 0;
else grid[i][j] = 1;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) continue;
if (i > 0) grid[i][j] += grid[i-1][j];
if (j > 0) grid[i][j] += grid[i][j-1];
if (i > 0 && j > 0) grid[i][j] -= grid[i-1][j-1];
}
}
vector<ll> ans;
for (int i = 0; i < q; i++) {
int curr = grid[b[i]][r[i]];
if (a[i] > 0) curr -= grid[a[i] - 1][r[i]];
if (l[i] > 0) curr -= grid[b[i]][l[i] - 1];
if (a[i] > 0 && l[i] > 0) curr += grid[a[i] - 1][l[i] - 1];
ans.push_back(curr);
}
return ans;
}
vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
n = X.size();
x = X;
y = Y;
q = T.size();
a = T;
b = B;
l = L;
r = R;
bool sub3 = n > 5000;
for (int i = 0; i < q; i++) if (a[i] != 0 || b[i] != 0) sub3 = false;
if (sub3) return solve3();
if (n <= 5000) return solve124();
return {-1};
}
/*
int main() {
vector<ll> k = mosaic({1, 0, 1, 0}, {1, 1, 0, 1}, {0, 2}, {3, 3}, {0, 0}, {3, 2});
for (auto x: k) cout << x << " ";
}*/
