#include "mosaic.h"
using namespace std;
#include <vector>
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();
int mosaic[N][N];
int countBLACK[N][N];
for (int i=0; i<N; i++) {
mosaic[0][i] = X[i];
mosaic[i][0] = Y[i];
if (i>0) {
countBLACK[0][i] = X[i]+countBLACK[0][i-1];
countBLACK[i][0] = Y[i]+countBLACK[i-1][0];
} else {
countBLACK[0][i] = X[i];
}
}
for (int i=1; i<N; i++) {
for (int j=1; j<N; j++) {
if (mosaic[i-1][j]==0 && mosaic[i][j-1]==0) {
mosaic[i][j] = 1;
} else {
mosaic[i][j] = 0;
}
countBLACK[i][j] = countBLACK[i-1][j]+countBLACK[i][j-1]+mosaic[i][j];
}
}
vector<long long> C(Q, 0);
for (int i=0; i<Q; i++) {
C[i] = countBLACK[B[i]][R[i]];
if (T[i] > 0) {
C[i]-=countBLACK[T[i]-1][R[i]];
}
if (L[i] > 0) {
C[i]-=countBLACK[B[i]][L[i]-1];
}
if (T[i] > 0 && L[i] > 0) {
C[i]+=countBLACK[T[i]-1][L[i]-1];
}
}
return C;
}
