#include "mosaic.h"
#include <vector>
#include <array>
#include <cstdio>
#include <algorithm>
#include <cstring>
using ll = long long;
using namespace std;
vector<ll> mosaic(vector<signed> X, vector<signed> Y,
vector<signed> T, vector<signed> B,
vector<signed> L, vector<signed> R) {
vector<ll> Ans(T.size());
int n = (int)X.size(), q = (int)T.size();
for (int i = 0; i < q; ++i) ++T[i], ++B[i], ++L[i], ++R[i];
for (auto mode : {'A', 'B'}) {
static int up[4][1 << 18], left[1 << 18][4];
memset(up, 0, sizeof up), memset(left, 0, sizeof left);
for (int i = 1; i <= n; ++i) {
up[1][i] = X[i - 1], left[i][1] = Y[i - 1];
if (i <= 3) up[i][1] = Y[i - 1], left[1][i] = X[i - 1];
}
for (int k : {2, 3}) for (int i = k; i <= n; ++i) {
up[k][i] = !up[k - 1][i] && !up[k][i - 1];
left[i][k] = !left[i - 1][k] && !left[i][k - 1];
if (i <= 3) up[i][k] |= left[i][k], left[k][i] = up[k][i];
}
static int diag_base[1 << 18];
static ll diag_rig[1 << 18], diag_lef[1 << 18];//, diag_base[1 << 18];
memset(diag_rig, 0, sizeof diag_rig);
memset(diag_lef, 0, sizeof diag_lef);
memset(diag_base, 0, sizeof diag_base);
for (int i = 1; i + 2 <= n; ++i) {
diag_base[i] = up[3][i + 2];
if (mode == 'B') diag_base[1] = 0;
diag_rig[i] = diag_base[i] * 1ll * i + diag_rig[i - 1];
diag_lef[i] = diag_base[i] * 1ll * (n - i) + diag_lef[i - 1];
diag_base[i] += diag_base[i - 1];
}
for (int i = 1; i <= 3; ++i) for (int j = 1; j <= n; ++j) up[i][j] += up[i - 1][j] + up[i][j - 1] - up[i - 1][j - 1];
for (int i = 1; i <= n; ++i) for (int j = 1; j <= 3; ++j) left[i][j] += left[i - 1][j] + left[i][j - 1] - left[i - 1][j - 1];
for (int i = 0; i < q; ++i) {
if (T[i] <= 3) {
int b = min(B[i], 3);
Ans[i] += up[b][R[i]] - up[b][L[i] - 1] - up[T[i] - 1][R[i]] + up[T[i] - 1][L[i] - 1];
T[i] = 4; B[i] = max(B[i], 3);
}
if (L[i] <= 3) {
int r = min(R[i], 3);
Ans[i] += left[B[i]][r] - left[T[i] - 1][r] - left[B[i]][L[i] - 1] + left[T[i] - 1][L[i] - 1];
L[i] = 4; R[i] = max(R[i], 3);
}
if (B[i] < T[i] || R[i] < L[i]) continue;
ll high = 1 + R[i] - T[i];
ll mid = L[i] - T[i] + 1;
ll low = L[i] - B[i] + 1;
if (high >= 1) {
if (mid <= 1) {
ll ximal = min(high, B[i] - T[i] + 1ll);
int pp = high - ximal + 1;
Ans[i] += diag_lef[high] - diag_lef[pp - 1] - ((diag_base[high] - diag_base[pp - 1]) * (n - high - 1ll))
+ (diag_base[pp - 1] * ximal);
} else {
ll ximal = min(high - mid + 1, B[i] - T[i] + 1ll);
int pp = high - ximal + 1;
Ans[i] += diag_lef[high] - diag_lef[pp - 1] - ((diag_base[high] - diag_base[pp - 1]) * (n - high - 1ll))
+ (diag_base[pp - 1] - diag_base[mid - 1]) * ximal;
ll Low = max(1ll, low);
ximal = R[i] - L[i] + 1;
if (ximal >= mid - low) {
Ans[i] += diag_rig[mid - 1] - diag_rig[Low - 1] + ((diag_base[mid - 1] - diag_base[Low - 1]) * (1ll - low));
} else {
int pp = Low + (ximal - min(ximal, Low - low + 1));
if (pp == Low) Ans[i] += (diag_base[mid - 1] - diag_base[Low - 1]) * ximal;
else Ans[i] += diag_rig[pp] - diag_rig[Low - 1] + ((diag_base[pp] - diag_base[Low - 1]) * (1ll - low))
+ (diag_base[mid - 1] - diag_base[pp]) * ximal;
}
}
}
swap(L[i], T[i]), swap(R[i], B[i]);
}
swap(X, Y);
}
return Ans;
}
