#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> mosaic(vector<int> X, vector<int> Y,
vector<int> T, vector<int> B,
vector<int> L, vector<int> R) {
const int n = X.size();
vector<vector<int>> grid(n, vector<int>(3));
swap(grid[0], X);
for (int i = 0; i < n; i++) {
grid[i][0] = Y[i];
}
for (int i = 1; i < min(3, n); i++) {
grid[i].resize(n);
for (int j = 1; j < n; j++) {
grid[i][j] = !(grid[i-1][j] || grid[i][j-1]);
}
}
for (int i = 3; i < n; i++) {
for (int j = 1; j < 3; j++) {
grid[i][j] = !(grid[i-1][j] || grid[i][j-1]);
}
}
vector<int> diag(2*n-1);
for (int i = 2; i < n; i++) {
if (grid[2][i]) {
diag[i-2 + n] = 1;
}
if (grid[i][2]) {
diag[2-i + n] = 1;
}
}
vector<int> diag_ps(2*n);
for (int i = 0; i < 2*n-1; i++) {
diag_ps[i+1] = diag_ps[i] + diag[i];
}
vector<vector<int>> ps(3, vector<int>(n+1));
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++) {
ps[i][j+1] = ps[i][j] + grid[i][j];
}
}
int q = (int)T.size();
vector<ll> C(q, 0);
for (int qq = 0; qq < q; qq++) {
assert(T[qq] == B[qq]);
if (T[qq] < 3) {
C[qq] = ps[T[qq]][R[qq]+1] - ps[T[qq]][L[qq]];
} else {
if (R[qq] < 3) {
int res = 0;
for (int i = L[qq]; i <= R[qq]; i++) {
res += grid[T[qq]][i];
}
C[qq] = res;
} else {
int res = 0;
for (int i = L[qq]; i < 3; i++) {
res += grid[T[qq]][i];
}
L[qq] = max(L[qq], 3);
res += diag_ps[R[qq] - T[qq] + n + 1] - diag_ps[L[qq] - T[qq] + n];
C[qq] = res;
}
}
}
return C;
}
//#include "grader.cpp"
