#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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();
std::vector<long long> C(Q, 0);
int n = X.size();
if (n == 1) return vector<ll>(Q, X[0]);
vector<vector<int>> grid(n, vector<int>(n));
for (int i = 0; i < n; ++i) grid[0][i] = X[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] == 0) grid[i][j] = 1;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i) grid[i][j] += grid[i - 1][j];
if (j) grid[i][j] += grid[i][j - 1];
if (i && j) grid[i][j] -= grid[i - 1][j - 1];
}
}
for (int i = 0; i < Q; ++i) {
ll res = grid[B[i]][R[i]];
if (T[i]) res -= grid[T[i] - 1][R[i]];
if (L[i]) res -= grid[B[i]][L[i] - 1];
if (T[i] && L[i]) res += grid[T[i] - 1][L[i] - 1];
C[i] = res;
}
return C;
}
