#include "mosaic.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<signed> X, Y, T, B, L, R;
vector<long long> C;
int N, Q;
void sub() {
vector<vector<bool>> grid(N, vector<bool>(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++) {
grid[i][j] = !(grid[i - 1][j] || grid[i][j - 1]);
}
}
vector<vector<int>> dp(N , vector<int> (N, 0));
for (int i = 0; i < N; i++) {
int l = 0;
for (int j = 0; j < N; j++) {
l += grid[i][j];
if (i) dp[i][j] = dp[i - 1][j];
dp[i][j] += l;
}
}
for (int i = 0; i < Q; i++) {
int ans = 0;
if (!L[i] && ! T[i]) ans = dp[B[i]][R[i]];
else {
ans = dp[B[i]][R[i]];
if (L[i]) ans -= dp[B[i]][L[i] - 1];
if (T[i]) ans -= dp[T[i] - 1][R[i]];
if (L[i] && T[i]) ans += dp[T[i] - 1][L[i] - 1];
}
C[i] = ans;
}
}
std::vector<long long> mosaic(std::vector<signed> X_, std::vector<signed> Y_,std::vector<signed> T_, std::vector<signed> B_, std::vector<signed> L_, std::vector<signed> R_) {
ios::sync_with_stdio(false);
cin.tie(0);
X = X_; Y = Y_; T = T_; B = B_; L = L_; R = R_;
Q = (int)T.size();
N = X.size();
C.resize(Q, 0);
if (N <= 3) {
sub();
return C;
}
vector<vector<bool>> line(3, vector<bool>(N)), column(3, vector<bool>(N));
for (int i = 0; i < N; i++) {
line[0][i] = X[i];
column[0][i] = Y[i];
}
line[1][0] = Y[1], line[2][0] = Y[2];
column[1][0] = X[1], column[2][0] = X[2];
for (int i = 1; i < 3; i++) {
for (int j = 1; j < N; j++) {
line[i][j] = !(line[i - 1][j] || line[i][j - 1]);
column[i][j] = !(column[i - 1][j] || column[i][j - 1]);
}
}
vector<vector<int>> dpLine(3 , vector<int> (N, 0)), dpColumn(3, vector<int>(N, 0));
for (int i = 0; i < 3; i++) {
int lLine = 0, lColumn = 0;
for (int j = 0; j < N; j++) {
lLine += line[i][j]; lColumn += column[i][j];
if (i) {
dpLine[i][j] = dpLine[i - 1][j];
dpColumn[i][j] = dpColumn[i - 1][j];
}
dpLine[i][j] += lLine, dpColumn[i][j] += lColumn;
}
}
vector<bool> diag(2 * N-1, false);
for (int i = 0; i <= N - 2; i++) {
diag[N + 1 - i] = column[2][i];
diag[N - 3 + i] = line[2][i];
}
vector<int> prefL(2 * N - 1, 0), prefR(2 * N-1, 0), pref(2 * N-1);
int cnt = 1;
for (int i = 0; i < 2 * N - 1; i++) {
if (i) {
prefL[i] = prefL[i - 1];
pref[i] = pref[i - 1];
prefR[2 * N - i - 2] = prefR[2 * N - i - 1];
}
prefL[i] += diag[i] * cnt;
prefR[2 * N - i - 2] += diag[2 * N - i - 2] * cnt;
pref[i] += diag[i];
cnt++;
}
/*for (int i = 0; i < 3; i++) {
prefL[i] = 0;
pref[i] = 0;
prefR[i] = 0;
prefL[2*N - 2 - i] = 0;
prefR[2*N - 2 - i] = 0;
pref[2*N - 2 - i] = 0;
}*/
for (int i = 0; i < Q; i++) {
int t = T[i], b = B[i], l = L[i], r = R[i];
if (t < 3) {
if (b < 3) {
C[i] += dpLine[b][r];
if (t) C[i] -= dpLine[t - 1][r];
if (l) C[i] -= dpLine[b][l - 1];
if (t && l) C[i] += dpLine[t - 1][l - 1];
continue;
}
else {
C[i] += dpLine[2][r];
if (t) C[i] -= dpLine[t - 1][r];
if (l) C[i] -= dpLine[2][l - 1];
if (t && l) C[i] += dpLine[t - 1][l - 1];
}
t = 3;
}
if (l < 3) {
if (r < 3) {
C[i] += dpColumn[r][b];
if (t) C[i] -= dpColumn[r][t - 1];
if (l) C[i] -= dpColumn[l - 1][b];
if (t && l) C[i] += dpColumn[l - 1][t - 1];
continue;
}
else {
C[i] += dpColumn[2][b];
if (t) C[i] -= dpColumn[2][t - 1];
if (l) C[i] -= dpColumn[l - 1][b];
if (t && l) C[i] += dpColumn[l - 1][t - 1];
}
l = 3;
}
int diag1 = N - 1 - b + l;
int diag2 = N - 1 - t + r;
int mid = (diag1 + diag2 + 1) / 2;
C[i] += prefL[mid] - prefL[diag1 - 1];
C[i] -= (pref[mid] - pref[diag1 - 1]) * diag1;
C[i] += prefR[mid + 1] - prefR[diag2 + 1];
C[i] -= (pref[diag2] - pref[mid]) * (2 * N - 2 - diag2);
int height = b - t + 1, large = r - l + 1, limit = min(height, large);
/*if (mid >= diag1 + limit - 1)*/C[i] -= prefL[mid] - prefL[diag1 + limit - 1] - (pref[mid] - pref[diag1 + limit - 1]) * (diag1 + limit);
/*if (mid + 1 - diag2 + limit - 1 <= 0)*/ C[i] -= prefR[mid + 1] - prefR[diag2 - limit + 1] - (pref[diag2 - limit]- pref[mid]) * (2 * N - 2 - diag2 + limit);
}
return C;
}
