#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ll long long int
#define cerr if(0) cerr
const int N = 5005;
int a[N][N], pref[N][N];
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 n = X.size();
int q = T.size();
vector<array<int, 3>> Q;
for(int i = 0; i < n; ++i) a[0][i] = X[i];
for(int i = 0; i < n; ++i) a[i][0] = Y[i];
for(int i = 1; i < n; ++i){
for(int j = 1; j < n ; ++j){
if(a[i - 1][j] == 0 && a[i][j - 1] == 0) a[i][j] = 1;
else a[i][j] = 0;
}
}
for(int i = 0; i < n; ++i){
for(int j = 0; j< n; ++j){
pref[i][j] = a[i][j];
if(i > 0) pref[i][j] += pref[i - 1][j];
if(j > 0) pref[i][j] += pref[i][j - 1];
if(i > 0 && j > 0) pref[i][j] -= pref[i - 1][j - 1];
}
}
vector<ll> C(q);
for(int i = 0; i < q; ++i){
int x1 = T[i], x2 = B[i];
int y1 = L[i], y2 = R[i];
C[i] = pref[x2][y2];
if(x1 > 0) C[i] -= pref[x1 - 1][y2];
if(y1 > 0) C[i] -= pref[x2][y1 - 1];
if(x1 > 0 && y1 > 0) C[i] += pref[x1-1][y1-1];
}
return C;
}
