#include "mosaic.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pii pair <ll, ll>
#define el '\n'
#define fr(i, l, r) for(ll (i) = l; (i) <= r; (i)++)
#define frb(i, r, l) for(ll (i) = r; (i) >= l; (i)--)
ll const N = 2e5 + 100;
ll pref[2][N], x[3][N], y[N][3];
unordered_map <ll, ll> skip, s1, s2, cnt;
ll f(ll a, ll b) {
if(!a || !b)
return 0;
ll res = 0;
//[1 - b; a - 1]
//x - y >= a - b
//[a - b; a - 1]
res += (a + 1) * (cnt[a - 1] - cnt[a - b - 1]);
res -= (s1[a - 1] - s1[a - b - 1]);
//x - y < a - b
//[1 - b; a - b - 1]
res += (b + 1) * (cnt[a - b - 1] - cnt[-b]);
res -= (s2[a - b - 1] - s2[-b]);
res -= skip[a - 1] - skip[-b];
return res;
}
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();
fr(i, 0, N - 1) {
pref[0][i] = X[i];
pref[1][i] = Y[i];
if(i) {
pref[0][i] += pref[0][i - 1];
pref[1][i] += pref[1][i - 1];
}
}
fr(j, 0, N - 1)
x[0][j] = X[j];
fr(i, 1, 2) {
x[i][0] = Y[i];
fr(j, 1, N - 1) {
ll val = x[i - 1][j] | x[i][j - 1];
val ^= 1;
x[i][j] = val;
if(!x[i][j] || (i >= 2 && j >= 2 && x[i - 1][j - 1]))
continue;
skip[i - j] = (i >= 2 && j >= 2);
s1[i - j] += i - skip[i - j];
s2[i - j] += j - skip[i - j];
cnt[i - j]++;
}
}
fr(j, 0, N - 1)
y[j][0] = Y[j];
fr(j, 1, 2) {
y[0][j] = X[j];
fr(i, 1, N - 1) {
ll val = y[i - 1][j] | y[i][j - 1];
val ^= 1;
y[i][j] = val;
if(i <= 2 || !y[i][j] || (i >= 2 && j >= 2 && y[i - 1][j - 1]))
continue;
skip[i - j] = (i >= 2 && j >= 2);
s1[i - j] += i - skip[i - j];
s2[i - j] += j - skip[i - j];
cnt[i - j]++;
}
}
fr(i, - N - 5, N + 5) {
skip[i] += skip[i - 1];
s1[i] += s1[i - 1];
s2[i] += s2[i - 1];
cnt[i] += cnt[i - 1];
}
vector <ll> ans(Q);
fr(i, 0, Q - 1) {
if(T[i] == 0) {
ans[i] += pref[0][R[i]];
if(L[i]) ans[i] -= pref[0][L[i] - 1];
T[i]++;
}
if(L[i] == 0) {
ans[i] += pref[1][B[i]];
ans[i] -= pref[1][T[i] - 1];
L[i]++;
}
if(T[i] > B[i] || L[i] > R[i])
continue;
ans[i] += f(B[i], R[i]);
ans[i] -= f(T[i] - 1, R[i]);
ans[i] -= f(B[i], L[i] - 1);
ans[i] += f(T[i] - 1, L[i] - 1);
}
return ans;
}
