#include <bits/stdc++.h>
using namespace std;
int add(int a, int b){
return a == 0 && b == 0;
}
vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R){
vector<vector<int>> layers(3);
int n = X.size(), q = T.size();
// flatten each layer
for (int i = n - 1; i >= 0; --i)
layers[0].push_back(Y[i]);
for (int i = 1; i < n; ++i)
layers[0].push_back(X[i]);
vector<int> pX = X, pY = Y;
for (int t = 1; t < min(n, 3); ++t){
vector<int> nX(n - t), nY(n - t);
nX[0] = nY[0] = add(pX[1], pY[1]);
for (int i = 1; i < n - t; ++i){
nX[i] = add(nX[i - 1], pX[i + 1]);
nY[i] = add(nY[i - 1], pY[i + 1]);
}
for (int i = n - t - 1; i >= 0; --i)
layers[t].push_back(nY[i]);
for (int i = 1; i < n - t; ++i)
layers[t].push_back(nX[i]);
pX.swap(nX), pY.swap(nY);
}
// cell (x, y) -> corresponding cell on layer[t] -> correct position in array
auto mp = [&](int t, int x, int y){
if (x <= y){
int d = x - t;
x = t, y -= d;
} else {
int d = y - t;
y = t, x -= d;
}
if (y == t) return n - x - 1;
else return n + y - 2 * t - 1;
};
vector<vector<int>> pref(3);
for (int t = 0; t < 3; ++t){
for (int x : layers[t]){
if (pref[t].empty()) pref[t].push_back(x);
else pref[t].push_back(pref[t].back() + x);
}
}
// for layers[2], need sth like sum(a[i] * i) and sum(a[i] * (n - i + 1))
vector<vector<long long>> f(2);
for (int i = 0; i < (int)layers[2].size(); ++i){
int val = layers[2][i] * (i + 1);
if (f[0].empty()) f[0].push_back(val);
else f[0].push_back(f[0].back() + val);
val = layers[2][i] * ((int)layers[2].size() - i);
if (f[1].empty()) f[1].push_back(val);
else f[1].push_back(f[1].back() + val);
}
auto get_sum = [&](int t, int l, int r){
if (l > r) return 0;
if (l == 0) return pref[t][r];
else return pref[t][r] - pref[t][l - 1];
};
auto get_sum_inc = [&](int l, int r){
if (l > r) return 0ll;
long long s = f[0][r];
if (l > 0) s -= f[0][l - 1];
s -= 1ll * l * get_sum(2, l, r);
return s;
};
auto get_sum_dec = [&](int l, int r){
if (l > r) return 0ll;
long long s = f[1][r];
if (l > 0) s -= f[1][l - 1];
return s - 1ll * ((int)f[1].size() - r - 1) * get_sum(2, l, r);
};
vector<long long> ans(q);
for (int i = 0; i < q; ++i){
if (T[i] < 2 || L[i] < 2){
if (T[i] == 0) ans[i] += get_sum(0, mp(0, 0, L[i]), mp(0, 0, R[i]));
if (T[i] >= 0 && T[i] < 2) ans[i] += get_sum(1, mp(1, 1, max(L[i], 1)), mp(1, 1, R[i]));
if (L[i] == 0) ans[i] += get_sum(0, mp(0, B[i], 0), mp(0, max(T[i], 1), 0));
if (L[i] >= 0 && L[i] < 2) ans[i] += get_sum(1, mp(1, B[i], 1), mp(1, max(T[i], 2), 1));
if (T[i] < 2) T[i] = 2;
if (L[i] < 2) L[i] = 2;
}
if (T[i] > B[i] || L[i] > R[i]) continue;
int left_most = mp(2, B[i], L[i]), right_most = mp(2, T[i], R[i]);
int m1 = mp(2, T[i], L[i]), m2 = mp(2, B[i], R[i]);
// cout << left_most << ' ' << m1 << ' ' << m2 << ' ' << right_most << '\n';
if (B[i] - T[i] <= R[i] - L[i]){
ans[i] += 1ll * get_sum(2, m1, m2) * (B[i] - T[i] + 1);
// cout << get_sum(2, m1, m2) * (B[i] - T[i] + 1) << '\n';
ans[i] += 1ll * get_sum_inc(left_most, m1 - 1);
// cout << get_sum_inc(left_most, m1 - 1) << '\n';
ans[i] += 1ll * get_sum_dec(m2 + 1, right_most);
// cout << get_sum_dec(m2 + 1, right_most) << '\n';
} else {
ans[i] += 1ll * get_sum(2, m2, m1) * (R[i] - L[i] + 1);
ans[i] += 1ll * get_sum_inc(left_most, m2 - 1);
ans[i] += 1ll * get_sum_dec(m1 + 1, right_most);
}
}
return ans;
}
