#include "mosaic.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
vi mosaic(vector<int32_t> X, vector<int32_t> Y,
vector<int32_t> T, vector<int32_t> B,
vector<int32_t> L, vector<int32_t> R) {
int N = X.size(),Q = T.size();
int rows[4][N+1]{},cols[4][N+1]{};
for (int i = 1;i<=N;i++) rows[1][i] = X[i-1];
for (int i = 1;i<=N;i++) cols[1][i] = Y[i-1];
for (int i=2;i<=N && i <= 3;i++) rows[i][1] = Y[i-1];
for (int i=2;i<=N && i<=3;i++) cols[i][1] = X[i-1];
set<int> diag;
for (int i = 2;i<=3;i++) {
for (int j = 2;j<=N;j++) {
rows[i][j] = (!rows[i-1][j] && !rows[i][j-1]);
if (rows[i][j]) diag.insert(i-j);
}
}
for (int i = 2;i<=3;i++) {
for (int j = 2;j<=N;j++) {
cols[i][j] = (!cols[i-1][j] && !cols[i][j-1]);
if (cols[i][j]) diag.insert(j-i);
}
}
if (N >= 4) {
int prv = cols[3][4];
for (int i = 4;i<=4;i++) {
for (int j = 4;j<=N;j++) {
prv = (!rows[3][j] && !prv);
if (prv) diag.insert(i-j);
}
}
prv = rows[3][4];
for (int i = 4;i<=4;i++) {
for (int j = 4;j<=N;j++) {
prv = (!cols[3][j] && !prv);
if (prv) {
diag.insert(j-i);
}
}
}
}
vi vals;
auto idx = [&](int x) {
return upper_bound(all(vals),x)-vals.begin();
};
for (int i=1-N;i<=N-1;i++) vals.push_back(i);
sort(all(vals));
vi pref(vals.size()+1,0ll);
for (auto it : diag) pref[idx(it)] = 1;
for (int i=1;i<=big(vals);i++) pref[i]+=pref[i-1];
vi ans(Q,0);
for (int i=1;i<=3;i++) {
for (int j = 2;j<=N;j++) rows[i][j] += rows[i][j-1];
}
for (int i = 0;i<Q;i++) {
L[i]++,R[i]++,T[i]++,B[i]++;
if (T[i] != B[i]) exit(-1);
if (T[i] <= 3) {
ans[i] = rows[T[i]][R[i]]-rows[T[i]][L[i]-1];
continue;
}
if (L[i] <= 3) {
for (int j = L[i];j<=3 && j<=R[i];j++) ans[i]+=cols[j][T[i]];
L[i]=4;
}
if (L[i] > R[i]) continue;
int st = idx(T[i]-L[i]),nd = idx(T[i]-R[i]);
ans[i]+=pref[st]-pref[nd-1];
}
return ans;
}
