#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mmod = 998244353;
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>
// Funkce mosaic
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){
ll n, q;
n = X.size();
q = T.size();
// 1. Příprava mřížky (tvůj původní kód)
vll row3;
vll col3;
vl x1, y1;
for (ll i = 0; i <n; i++){
x1.push_back(X[i]);
y1.push_back(Y[i]);
}
row3.push_back(x1); col3.push_back(y1);
row3.push_back({Y[1]}); row3.push_back({Y[2]});
col3.push_back({X[1]}); col3.push_back({X[2]});
for (ll i = 1; i < 3; i++){
for (ll j = 1; j < n; j++){
ll v1 = 0; ll v2 = 0;
if (row3[i][j-1] == 0 && row3[i-1][j] == 0){
v1 = 1;
}
if (col3[i][j-1] == 0 && col3[i-1][j] == 0){
v2 = 1;
}
row3[i].push_back(v1);
col3[i].push_back(v2);
}
}
// 2. Linearizace do s1, s2, s3 (tvůj původní kód)
vl s1, s2, s3;
for (ll i = n-1; i>=0; i--){
s1.push_back(col3[0][i]);
}
for (ll i = 1; i < n; i++){
s1.push_back(row3[0][i]);
}
for (ll i = n-1; i>=1; i--){
s2.push_back(col3[1][i]);
}
for (ll i = 2; i < n; i++){
s2.push_back(row3[1][i]);
}
for (ll i = n-1; i>=2; i--){
s3.push_back(col3[2][i]);
}
for (ll i = 3; i < n; i++){
s3.push_back(row3[2][i]);
}
// 3. Prefixové součty
// Změna: p1, p2, p3 inicializujeme s {0}, aby p[i] byl součet prvních i prvků
vl p1 = {0}, p2 = {0}, p3 = {0};
for (ll x : s1) p1.push_back(p1.back() + x);
for (ll x : s2) p2.push_back(p2.back() + x);
for (ll x : s3) p3.push_back(p3.back() + x);
// Vážený prefixový součet pro Layer 3 (místo q2)
vl q1 = {0};
for (ll i = 0; i < s3.size(); i++){
q1.push_back(q1.back() + s3[i] * (i + 1));
}
// q2 jsme smazali, není potřeba
vl ans;
for (ll i = 0; i < q; i++){
ll l, r, u, d;
l = L[i]; r = R[i]; u = T[i]; d = B[i];
ll a, b;
ll suma = 0;
// --- Layer 1 ---
b = 0; a = 1e9;
if (l == 0){
a = min(a, n-d-1);
b = max(b, n-u);
}
if (u == 0){
a = min(a, n + l - 1);
b = max(b, n + r);
}
if (a < b){
suma += p1[b] - p1[a];
}
// --- Layer 2 ---
b = 0; a = 1e9;
if (l <= 1 && r >= 1){
a = min(a, n-d-1);
b = max(b, n-max(u,1ll));
}
if (u <= 1 && d >= 1){
a = min(a, n + max(l,1ll) - 3);
b = max(b, n + r - 2);
}
if (a < b){
suma += p2[b] - p2[a];
}
// --- Layer 3 (OPRAVENO) ---
// Podmínka && je nutná, jinak saháme mimo pole s3
if (r >= 2 && d >= 2){
ll l_in = max(2ll, (ll)l);
ll u_in = max(2ll, (ll)u);
// Ověříme, zda oříznutý obdélník dává smysl
if (l_in <= r && u_in <= d) {
ll a = l_in - 2 + (n - 1) - d;
ll b = r - 2 + n - u_in;
ll t = min(d - u_in, r - l_in); // tloušťka
// Metoda středu (řeší překryvy trojúhelníků)
ll mid = (a + b) / 2;
ll end_rise = min(a + t, mid); // Konec náběhu
ll start_fall = max(b - t, mid + 1); // Začátek poklesu
// 1. Rostoucí část (Rising)
// Váha roste: s3[k] * (k - a + 1)
// Suma = (q1[R] - q1[L]) - a * (p3[R] - p3[L])
if (a <= end_rise) {
suma += (q1[end_rise + 1] - q1[a]);
suma -= (p3[end_rise + 1] - p3[a]) * a;
}
// 2. Klesající část (Falling)
// Váha klesá: s3[k] * (b - k + 1) -> (b+2 - (k+1))
// Suma = (b+2)*(p3[R] - p3[L]) - (q1[R] - q1[L])
if (start_fall <= b) {
ll range_sum = p3[b + 1] - p3[start_fall];
ll range_w_sum = q1[b + 1] - q1[start_fall];
suma += range_sum * (b + 2) - range_w_sum;
}
// 3. Plošina (Plateau)
// Váha je konstantní: t + 1
if (end_rise + 1 < start_fall) {
suma += (p3[start_fall] - p3[end_rise + 1]) * (t + 1);
}
}
}
ans.push_back(suma);
}
return ans;
}
// Main pro testování (pokud potřebuješ)
int main() {
// Zde můžeš vložit testovací vstup
return 0;
}
