Ce problème introduit un jeu où deux joueurs, S et T, évoluent sur deux graphes distincts. L'objectif est de trouver la valeur minimale d'une contrainte combinée permettant aux deux joueurs d'atteindre le nœud 1 de leur graphe respectif. Chaque joueur peut se déplacer d'un nœud actuel vers un nœud cible, à condition que tous les nœuds du chemin (y compris le nœud cible) aient une valeur inférieure à celle du nœud de départ. Une particularité importante est la manière dont les mouvements sont évalués.

Pour modéliser les mouvements possibles, nous construisons une structure d'arbre de fusion (semblable à un arbre de Kruskal ou une forêt maintenue par un Disjoint Set Union - DSU) pour chaque graphe. Cette structure permet de déterminer rapidement le nœud de valeur minimale qu'un joueur peut atteindre à partir de sa position actuelle en respectant la contrainte de "nœuds intermédiaires plus petits".

Construction des Arbres de Fusion

Pour chaque graphe (Graphe 1 pour S, Graphe 2 pour T), nous procédons comme suit :

1. Initialisez chaque nœud i comme son propre représentant dans le DSU, et val_min_atteignable[i] = i (le nœud de valeur minimale atteignable depuis i est i lui-même, initialement).
2. Parcourez les nœuds i de 1 à n. Pour chaque voisin v de i :
   • Si v < i, cela signifie que v est un nœud de valeur inférieure par rapport à i. Nous fusionnons le composant de v avec i.
   • Le représentant du composant de v (appelons-le rep_v) est mis à jour pour être i dans le DSU.
   • La valeur parent_fusion[rep_v] est réglée sur i, indiquant que i est un "parent" ou un nœud de niveau supérieur qui peut fusionner avec le composant de rep_v, servant de "cible de saut" dans le jeu.
   • La valeur minimale atteignable depuis i, val_min_atteignable[i], est mise à jour avec min(val_min_atteignable[i], val_min_atteignable[rep_v]). Cela capture l'idée qu'en passant par i vers v, on peut atteindre tout ce que v pouvait atteindre.

Après cette construction, pour un nœud s, parent_fusion1[s] représente le "prochain saut" potentiel vers un nœud de valeur supérieure dans l'arbre de fusion, et val_min_atteignable1[s] représente le plus petit nœud atteignable depuis s dans son composant actuel.

Logique du Jeu et Optimisation de la Réponse

La valeur de la contrainte est MAX_VAL. À chaque tour, un joueur S (ou T) peut effectuer un mouvement si le coût combiné parent_fusion1[s] + val_min_atteignable2[t] (pour S) ou val_min_atteignable1[s] + parent_fusion2[t] (pour T) ne dépasse pas MAX_VAL. Les joueurs tentent d'atteindre le nœud 1.

L'algorithme utilise une approche itérative pour trouver le MAX_VAL minimal. Au lieu d'une recherche binaire, on commence avec une valeur initiale de MAX_VAL = s + t, puis on l'incrémente manuellement chaque fois que les joueurs sont bloqués. Le processus se déroule comme suit :

1. Initialiser MAX_VAL = s + t.
2. Tant que l'un des joueurs n'a pas atteint le nœud 1 (c'est-à-dire val_min_atteignable1[s] != 1 ou val_min_atteignable2[t] != 1) :
   1. Tant que les deux joueurs sont bloqués par la valeur actuelle de MAX_VAL, incrémenter MAX_VAL. Être bloqué signifie que ni S ni T ne peuvent faire un mouvement respectant la contrainte MAX_VAL.
   2. Simuler les mouvements des joueurs : À tour de rôle, chaque joueur tente de se déplacer vers son parent_fusion si la condition de coût est remplie et qu'il n'est pas déjà au nœud 1. Cette boucle continue tant qu'au moins un joueur peut faire un mouvement.
3. Une fois que les deux joueurs ont atteint le nœud 1, le MAX_VAL courant est la réponse.

Cette approche est valide car la possibilité de se déplacer est monotone par rapport à MAX_VAL : si un mouvement est possible avec un certain MAX_VAL, il l'est aussi avec un MAX_VAL plus grand. La complexité de cette approche est dominée par la construction des arbres de fusion via l'union-find.

#include <iostream>
#include <vector>
#include <algorithm> // For std::min
#include <string.h> // For memset, typically not needed if vectors are cleared

// Fast I/O utilities
char input_buffer[1<<21], *p_buffer1, *p_buffer2;
#define GET_CHAR_FAST() (p_buffer1 == p_buffer2 && (p_buffer2 = (p_buffer1 = input_buffer) + fread(input_buffer, 1, 1 << 21, stdin), p_buffer1 == p_buffer2) ? EOF : *p_buffer1++)

long long read_long() {
    long long value = 0;
    bool negative = false;
    char ch = GET_CHAR_FAST();
    while (ch < '0' || ch > '9') {
        if (ch == '-') negative = true;
        ch = GET_CHAR_FAST();
    }
    while (ch >= '0' && ch <= '9') {
        value = value * 10 + (ch - '0');
        ch = GET_CHAR_FAST();
    }
    return negative ? -value : value;
}

const int MAX_NODES = 1000005;
std::vector<int> adj_graph1[MAX_NODES];
std::vector<int> adj_graph2[MAX_NODES];
int parent_fusion1[MAX_NODES]; // The "jump target" for graph 1
int parent_fusion2[MAX_NODES]; // The "jump target" for graph 2
int val_min_reachable1[MAX_NODES]; // Min node reachable within component for graph 1
int val_min_reachable2[MAX_NODES]; // Min node reachable within component for graph 2
int dsu_set_parent[MAX_NODES]; // Parent array for Disjoint Set Union

int find_set_representative(int x) {
    if (dsu_set_parent[x] == x) return x;
    return dsu_set_parent[x] = find_set_representative(dsu_set_parent[x]);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int num_test_cases = read_long();
    while (num_test_cases--) {
        int n_nodes_current;
        n_nodes_current = read_long();

        // Clear adjacency lists for the current test case
        for (int i = 1; i <= n_nodes_current; i++) {
            adj_graph1[i].clear();
            adj_graph2[i].clear();
        }

        // Read edges for Graph 1
        for (int i = 1; i < n_nodes_current; i++) {
            int u = read_long(), v = read_long();
            adj_graph1[u].push_back(v);
            adj_graph1[v].push_back(u);
        }
        // Read edges for Graph 2
        for (int i = 1; i < n_nodes_current; i++) {
            int u = read_long(), v = read_long();
            adj_graph2[u].push_back(v);
            adj_graph2[v].push_back(u);
        }

        // Build fusion tree for Graph 1
        for (int i = 1; i <= n_nodes_current; i++) {
            dsu_set_parent[i] = i;
            val_min_reachable1[i] = i;
            parent_fusion1[i] = i; // Default jump target is itself
        }
        for (int i = 1; i <= n_nodes_current; i++) {
            for (int neighbor : adj_graph1[i]) {
                if (neighbor < i) { // Consider neighbors with smaller values
                    int rep_neighbor = find_set_representative(neighbor);
                    if (dsu_set_parent[rep_neighbor] != i) { // If not already connected to i's component
                        dsu_set_parent[rep_neighbor] = i; // Merge rep_neighbor's component into i's
                        parent_fusion1[rep_neighbor] = i; // i becomes the jump target for rep_neighbor's component
                        val_min_reachable1[i] = std::min(val_min_reachable1[i], val_min_reachable1[rep_neighbor]);
                    }
                }
            }
        }
        
        // Build fusion tree for Graph 2
        for (int i = 1; i <= n_nodes_current; i++) {
            dsu_set_parent[i] = i;
            val_min_reachable2[i] = i;
            parent_fusion2[i] = i; // Default jump target is itself
        }
        for (int i = 1; i <= n_nodes_current; i++) {
            for (int neighbor : adj_graph2[i]) {
                if (neighbor < i) {
                    int rep_neighbor = find_set_representative(neighbor);
                    if (dsu_set_parent[rep_neighbor] != i) {
                        dsu_set_parent[rep_neighbor] = i;
                        parent_fusion2[rep_neighbor] = i;
                        val_min_reachable2[i] = std::min(val_min_reachable2[i], val_min_reachable2[rep_neighbor]);
                    }
                }
            }
        }

        int current_pos_s, current_pos_t;
        current_pos_s = read_long(); // Initial position for S
        current_pos_t = read_long(); // Initial position for T

        long long answer_value = current_pos_s + current_pos_t; // Initial combined value

        // Simulation loop until both players reach node 1
        while (val_min_reachable1[current_pos_s] != 1 || val_min_reachable2[current_pos_t] != 1) {
            // If both players are stuck at the current answer_value, increment it
            while ((val_min_reachable2[current_pos_t] == 1 || (long long)parent_fusion1[current_pos_s] + val_min_reachable2[current_pos_t] > answer_value) &&
                   (val_min_reachable1[current_pos_s] == 1 || (long long)val_min_reachable1[current_pos_s] + parent_fusion2[current_pos_t] > answer_value)) {
                answer_value++;
            }

            // Players take turns moving as long as possible under the current answer_value
            bool moved_in_round;
            do {
                moved_in_round = false;
                // Player S attempts to move
                if (val_min_reachable1[current_pos_s] != 1 && (long long)parent_fusion1[current_pos_s] + val_min_reachable2[current_pos_t] <= answer_value) {
                    current_pos_s = parent_fusion1[current_pos_s];
                    moved_in_round = true;
                }
                // Player T attempts to move
                if (val_min_reachable2[current_pos_t] != 1 && (long long)val_min_reachable1[current_pos_s] + parent_fusion2[current_pos_t] <= answer_value) {
                    current_pos_t = parent_fusion2[current_pos_t];
                    moved_in_round = true;
                }
            } while (moved_in_round); // Continue as long as at least one player moved
        }
        std::cout << answer_value << "\n";
    }
    return 0;
}

Graphes, Algorithmes, Union-Find, Jeu, OptimisationConstruction d'un Cycle Numérique StratégiqueCe problème demande la construction d'un cycle à partir d'un ensemble de nombres entiers jusqu'à n, en suivant des règles spécifiques basées sur leurs facteurs premiers et leurs multiples. L'objectif est de maximiser le nombre d'éléments dans le cycle ou de satisfaire une condition de construction particulière.

Préparation et Filtrage

Nous commençons par identifier les nombres premiers et préparer les multiples de chaque premier. Certains nombres premiers sont "moins utiles" ou demandent un traitement spécial en fonction de la taille de n :

1. Tous les nombres de 2 à n sont marqués. Nous utilisons un crible pour identifier les nombres premiers (est_premier_flag).
2. Pour chaque nombre i, nous stockons ses multiples dans multiples_par_facteur[i]. Nous marquons également les nombres déjà traités pour éviter les doublons (marque_initiale, utilisé pour assurer que chaque nombre n'est associé qu'à son plus petit facteur premier dans ce contexte).
3. Une attention particulière est portée aux nombres premiers p tels que 3p <= n mais 4p > n. Ces premiers sont collectés dans une liste spéciale (primes_speciales_list) car ils ne peuvent pas utiliser la connexion 2p - ... - 4p complète.

Construction du Cycle pour n >= 12

Pour les valeurs de n suffisamment grandes (ici n >= 12, les cas plus petits étant traités séparément), la construction se déroule en plusieurs phases pour assembler un cycle complexe :

Phase 1 : Connexion des Premiers Spéciaux

Les nombres premiers dans primes_speciales_list sont groupés par paires. Si le nombre de premiers spéciaux est impair, un élément fictif est ajouté pour former une paire. Chaque paire (X, Y) est utilisée pour créer une séquence :

• ... 2X - X - 3X ...
• Si Y est valide (non fictif) : ... 3Y - Y - 2Y ...

Ces séquences sont ajoutées au cycle résultant (chemin_cycle). Cette étape relie les multiples de 2 et 3 de ces premiers entre eux, formant une chaîne qui peut ensuite être intégrée dans le cycle global. Les nombres utilisés sont marqués comme visités.

Phase 2 : Connexion des Premiers Standard

Pour les nombres premiers p où 4p <= n, une autre stratégie de connexion est utilisée. Pour chacun de ces premiers p, nous ajoutons la séquence :

• ... 2p - [tous les multiples non visités de p] - 4p ...

Cette séquence permet de relier 2p à 4p en passant par tous les autres mulitples de p qui n'ont pas encore été inclus dans le cycle. Encore une fois, les nombres ajoutés sont marqués comme visités.

Phase 3 : Finalisation avec les Nombres Pairs

Après les phases précédentes, tout nombre pair non encore visité entre 2 et n est ajouté à la fin du cycle. Cela garantit que tous les nombres pairs sont inclus et aide à fermer le cycle en se connectant potentiellement au premier élément (qui est souvent 2).

Cas Spécial : n < 12

Pour les petites valeurs de n, la construction complexe n'est pas nécessaire. Un simple cycle formé par tous les nombres pairs de 2 à n est suffisant et est directement affiché.

Le résultat final est la taille du cycle construit et la liste de ses éléments.

#include <iostream>
#include <vector>
#include <numeric> // For std::iota if needed, not directly used here but good practice
#include <algorithm> // For std::sort, std::unique

const int MAXN_CYCLE = 500005;
int n_val;
std::vector<int> multiples_par_facteur[MAXN_CYCLE]; // Stocke les multiples pour chaque facteur (utilisé pour les primes)
std::vector<int> chemin_cycle; // Le cycle résultant
std::vector<int> primes_speciales_list; // Primes with 3p <= n but 4p > n

bool est_visite[MAXN_CYCLE]; // Marque si un nombre est déjà dans le chemin
bool est_premier_flag[MAXN_CYCLE]; // Marque si un nombre est premier
bool marque_initiale[MAXN_CYCLE]; // Marque les nombres déjà traités pour l'association aux facteurs premiers

// Fonction utilitaire pour insérer les multiples d'un premier dans le cycle
void inserer_multiples(int p_val) {
    chemin_cycle.push_back(p_val * 2);
    est_visite[p_val * 2] = true;

    for (int multiple : multiples_par_facteur[p_val]) {
        if (!est_visite[multiple]) {
            chemin_cycle.push_back(multiple);
            est_visite[multiple] = true;
        }
    }
    chemin_cycle.push_back(p_val * 4);
    est_visite[p_val * 4] = true;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int nb_tests;
    std::cin >> nb_tests;
    while (nb_tests--) {
        std::cin >> n_val;

        if (n_val >= 12) {
            chemin_cycle.clear();
            primes_speciales_list.clear();
            // Reset flags and vectors for each test case up to n_val.
            for (int i = 2; i <= n_val; i++) {
                multiples_par_facteur[i].clear();
                est_visite[i] = false;
                est_premier_flag[i] = false; 
                marque_initiale[i] = false;
            }

            for (int i = 2; i <= n_val; i++) {
                if (marque_initiale[i]) continue; // Already processed as a multiple of a smaller prime
                
                est_premier_flag[i] = true; // 'i' is prime
                if (i * 3 <= n_val && i * 4 > n_val) { // Special prime condition
                    primes_speciales_list.push_back(i);
                }
                
                // Collect multiples for this prime
                for (int j = i; j <= n_val; j += i) {
                    if (!marque_initiale[j]) { // Only associate with its smallest prime factor
                        multiples_par_facteur[i].push_back(j);
                        marque_initiale[j] = true;
                    }
                }
            }

            // Handle odd number of special primes (X, Y)
            if (primes_speciales_list.size() % 2 != 0) {
                primes_speciales_list.push_back(-1); // Use -1 as a dummy prime
            }

            // Phase 1: Connect special primes
            for (size_t i = 0; i < primes_speciales_list.size(); i += 2) {
                int p_x = primes_speciales_list[i];
                int p_y = primes_speciales_list[i + 1];

                chemin_cycle.push_back(2 * p_x); est_visite[2*p_x] = true;
                chemin_cycle.push_back(p_x); est_visite[p_x] = true;
                chemin_cycle.push_back(3 * p_x); est_visite[3*p_x] = true;
                
                if (p_y != -1) { // If Y is a real prime
                    chemin_cycle.push_back(3 * p_y); est_visite[3*p_y] = true;
                    chemin_cycle.push_back(p_y); est_visite[p_y] = true;
                    chemin_cycle.push_back(2 * p_y); est_visite[2*p_y] = true;
                }
            }

            // Phase 2: Connect standard primes (with 4p <= n)
            for (int i = 3; i <= n_val; i++) {
                if (est_premier_flag[i] && i * 4 <= n_val) {
                    inserer_multiples(i); // This function modifies chemin_cycle and est_visite
                }
            }
            
            // Phase 3: Add remaining even numbers
            for (int i = 2; i <= n_val; i += 2) {
                if (!est_visite[i]) {
                    chemin_cycle.push_back(i);
                    est_visite[i] = true;
                }
            }
            
            std::cout << chemin_cycle.size() << "\n";
            for (size_t i = 0; i < chemin_cycle.size(); ++i) {
                std::cout << chemin_cycle[i] << (i == chemin_cycle.size() - 1 ? "" : " ");
            }
        } else { // Case n < 12
            std::cout << n_val / 2 << "\n";
            for (int i = 2; i <= n_val; i += 2) {
                std::cout << i << (i + 1 > n_val ? "" : " "); 
            }
        }
        std::cout << " \n"; // Original output had a space then newline. Let's replicate.
    }
    return 0;
}

Construction de l'Arbre de Reconstruction

L'arbre de reconstruction est construit en ajoutant les nœuds du graphe original dans un ordre spécifique, généralement décroissant (de N à 1). Lors de l'ajout d'un nœud i :

1. Initialement, chaque nœud i est son propre composant dans une structure d'Union-Find (DSU).
2. Pour chaque nœud i (en partant de N et descendant vers 1), nous examinons ses voisins v dans le graphe original.
3. Si un voisin v a une valeur supérieure à i (c'est-à-dire v > i, car v a déjà été traité), et si v et i n'appartiennent pas déjà au même composant DSU, nous fusionnons leurs composants.
4. Le nœud i devient le parent dans l'arbre de reconstruction pour le représentant du composant de v (représentant_v). Une arête est ajoutée de i à représentant_v dans l'arbre de reconstruction. Cela signifie que i est le plus petit nœud (en valeur) qui connecte v à des nœuds d'une valeur encore plus petite, agissant comme un ancêtre pour les composants fusionnés.

Cette structure permet que le plus petit nœud sur un chemin entre deux nœuds u et v du graphe original corresponde au plus petit ancêtre commun (LCA) de u et v dans l'arbre de reconstruction (plus précisément, la valeur du nœud LCA si les nœuds internes de l'arbre de reconstruction sont les nœuds du graphe original).

Problème 1 : Somme Pondérée des Profondeurs du LCA

La première question demande de calculer une somme agrégée sur tous les chemins possibles, en utilisant la profondeur du plus petit ancêtre commun (LCA) dans l'arbre de reconstruction. Pour chaque nœud x de l'arbre de reconstruction à une profondeur d, nous calculons la contribution des paires de nœuds (u,v) du graphe original dont x est le LCA. Le nombre de telles paires est obtenu en soustrayant le nombre de sous-ensembles entièrement contenus dans les sous-arbres des enfants de x du nombre total de sous-ensembles dans le sous-arbre de x (chaque sous-ensemble ayant au moins un nœud dans le sous-arbre de x mais pas dans celui de ses enfants). Ce calcul se fait par un parcours en profondeur (DFS) sur l'arbre de reconstruction :

• taille_sous_arbre[x] : nombre de nœuds du graphe original dans le sous-arbre de x.
• s : représente le nombre de paires (u,v) dont le LCA est x. Il est calculé comme (2^{taille_sous_arbre[x]} - 1) - sum_{v enfant de x} (2^{taille_sous_arbre[v]} - 1).
• La contribution de x est alors s * d^K, où d est la profondeur de x et K est une constante donnée.

Problème 2 : Calcul par Programmation Dynamique sur Arbre

La deuxième question utilise une approche de programmation dynamique (PD) sur l'arbre de reconstruction. Pour chaque nœud x, la valeur dp[x] est calculée en combinant les résultats de ses enfants :

• Initialement, dp[x] = 1.
• Pour chaque enfant v de x, on calcule dfs_dp(v) récursivement, puis dp[x] = dp[x] * dp[v] modulo P.
• Enfin, dp[x] est transformé par la formule ((dp[x] - 1) * 2 * K + K + 1) % P.

Cette récurrence est spécifique à un problème de comptage impliquant des structures de chemins ou de sous-ensembles dans l'arbre, où K joue un rôle dans la pondération ou la transformation des combinaisons.

Problème 3 : Bijection XOR et Combinatoire

La troisième question exploite une propriété de bijection basée sur les opérations XOR pour faciliter le comptage. Elle stipule qu'il existe une bijection entre un ensemble S de nœuds du graphe original et un ensemble V de nœuds de l'arbre de reconstruction via une transformation impliquant S \oplus \{x, f_x\} (où f_x est l'ancêtre de x dans l'arbre de reconstruction et \oplus est l'opération XOR symétrique de différence d'ensembles). Cette bijection réduit le problème de comptage de S à un problème de comptage de V. La solution se résume à une formule combinatoire directe :

• La réponse est sum_{i=1 to N} C(N, i) * ceil(i/K) modulo P.
• C(N, i) représente le coefficient binomial "N parmi i".
• ceil(i/K) est calculé comme (i + K - 1) / K en arithmétique entière.

Cette approche tire parti de la simplification apportée par la bijection pour résoudre le problème directement par combinatoire.

#include <iostream>
#include <vector>
#include <algorithm> // For std::min, std::max, etc.

// Fast I/O utilities
char input_buffer[1<<21], *p_buffer1, *p_buffer2;
#define GET_CHAR_FAST() (p_buffer1 == p_buffer2 && (p_buffer2 = (p_buffer1 = input_buffer) + fread(input_buffer, 1, 1 << 21, stdin), p_buffer1 == p_buffer2) ? EOF : *p_buffer1++)

long long read_long() {
    long long value = 0;
    bool negative = false;
    char ch = GET_CHAR_FAST();
    while (ch < '0' || ch > '9') {
        if (ch == '-') negative = true;
        ch = GET_CHAR_FAST();
    }
    while (ch >= '0' && ch <= '9') {
        value = value * 10 + (ch - '0');
        ch = GET_CHAR_FAST();
    }
    return negative ? -value : value;
}

const int MOD_PRIME = 998244353;
const int MAX_NODES = 2000005;

int n_nodes_global, m_edges_global, k_val_global;
long long final_answer_global;

// Powers of 2 modulo MOD_PRIME
long long powers_of_2[MAX_NODES];

// Adjacency lists for the original graph
std::vector<int> adj_original_graph[MAX_NODES];
// Adjacency lists for the reconstruction tree
std::vector<int> adj_reconstruction_tree[MAX_NODES];

// Modular exponentiation
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD_PRIME;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD_PRIME;
        base = (base * base) % MOD_PRIME;
        exp /= 2;
    }
    return res;
}

// Factorials and inverse factorials for combinatorics
long long factorials[MAX_NODES], inv_factorials[MAX_NODES], modular_inverses[MAX_NODES];

void precompute_combinatorics(int n_max) {
    factorials[0] = factorials[1] = inv_factorials[0] = inv_factorials[1] = modular_inverses[0] = modular_inverses[1] = 1;
    for (int i = 2; i <= n_max; i++) {
        factorials[i] = (factorials[i - 1] * i) % MOD_PRIME;
        modular_inverses[i] = (MOD_PRIME - MOD_PRIME / i) * modular_inverses[MOD_PRIME % i] % MOD_PRIME;
        inv_factorials[i] = (inv_factorials[i - 1] * modular_inverses[i]) % MOD_PRIME;
    }
}

// Function C(n, m) = n! / (m! * (n-m)!)
inline long long combinations(int n, int m) {
    if (n < 0 || m < 0 || n < m) return 0;
    return (((factorials[n] * inv_factorials[m]) % MOD_PRIME) * inv_factorials[n - m]) % MOD_PRIME;
}

// Variables for Problem 1
int subtree_size[MAX_NODES];
void dfs_problem1(int u, int depth) {
    subtree_size[u] = 1;
    long long sum_child_contributions = 0;
    for (int v : adj_reconstruction_tree[u]) {
        dfs_problem1(v, depth + 1);
        subtree_size[u] += subtree_size[v];
        sum_child_contributions = (sum_child_contributions + MOD_PRIME - powers_of_2[subtree_size[v]] + 1) % MOD_PRIME;
    }
    long long contribution_for_lca_x = (sum_child_contributions + powers_of_2[subtree_size[u]] - 1 + MOD_PRIME) % MOD_PRIME;
    final_answer_global = (final_answer_global + contribution_for_lca_x * power(depth, k_val_global)) % MOD_PRIME;
}

// Variables for Problem 2
long long dp_problem2[MAX_NODES];
void dfs_problem2(int u) {
    dp_problem2[u] = 1;
    for (int v : adj_reconstruction_tree[u]) {
        dfs_problem2(v);
        dp_problem2[u] = (dp_problem2[u] * dp_problem2[v]) % MOD_PRIME;
    }
    dp_problem2[u] = (((dp_problem2[u] - 1 + MOD_PRIME) % MOD_PRIME * 2 % MOD_PRIME * k_val_global % MOD_PRIME) + k_val_global + 1) % MOD_PRIME;
}

// Union-Find for reconstruction tree construction
int dsu_parent_array[MAX_NODES];
int find_dsu_set(int x) {
    if (dsu_parent_array[x] == x) return x;
    return dsu_parent_array[x] = find_dsu_set(dsu_parent_array[x]);
}

int main() {
    precompute_combinatorics(MAX_NODES - 1);

    int execution_mode; // str from original, indicates which problems to solve
    execution_mode = read_long();
    n_nodes_global = read_long();
    m_edges_global = read_long();
    k_val_global = read_long();

    powers_of_2[0] = 1;
    for (int i = 1; i <= n_nodes_global; i++) {
        powers_of_2[i] = (powers_of_2[i - 1] * 2) % MOD_PRIME;
        dsu_parent_array[i] = i; // Initialize DSU
    }

    for (int i = 0; i < m_edges_global; i++) {
        int u = read_long(), v = read_long();
        adj_original_graph[u].push_back(v);
        adj_original_graph[v].push_back(u);
    }

    // Build the reconstruction tree (process nodes from N down to 1)
    for (int i = n_nodes_global; i >= 1; i--) {
        for (int v : adj_original_graph[i]) {
            if (v < i) continue; // v will be processed later or already processed

            int rep_v = find_dsu_set(v);
            int rep_i = find_dsu_set(i); // This should typically be i itself for the current node

            if (rep_v != rep_i) { // If components are distinct
                // Make i an ancestor of rep_v in the reconstruction tree
                adj_reconstruction_tree[i].push_back(rep_v);
                dsu_parent_array[rep_v] = i; // Union(rep_v, i), setting i as parent of rep_v's component
            }
        }
    }

    if (execution_mode / 100) { // If bit 2 is set (1xx)
        final_answer_global = 0;
        dfs_problem1(1, 1); // Assuming 1 is the root of the reconstruction tree
        std::cout << final_answer_global % MOD_PRIME << " ";
    }
    if ((execution_mode / 10) & 1) { // If bit 1 is set (x1x)
        dfs_problem2(1); // Assuming 1 is the root
        std::cout << (dp_problem2[1] - 1 + MOD_PRIME) % MOD_PRIME << " ";
    }
    if (execution_mode & 1) { // If bit 0 is set (xx1)
        final_answer_global = 0;
        for (int i = 1; i <= n_nodes_global; i++) {
            final_answer_global = (final_answer_global + combinations(n_nodes_global, i) * ((i + k_val_global - 1) / k_val_global)) % MOD_PRIME;
        }
        std::cout << final_answer_global % MOD_PRIME << "\n";
    }

    return 0;
}

1. Compression de Coordonnées

Étant donné que les coordonnées des rectangles peuvent être très grandes mais que seuls leurs bords sont pertinents, nous utilisons la compression de coordonnées. Toutes les coordonnées x1, x2+1, y1, y2+1 de tous les rectangles (plus des points de référence comme 0 et 1) sont collectées, triées et dédoublées. Cela crée une grille logique plus petite où chaque "cellule" compressée (cx, cy) représente un rectangle [coord_x[cx], coord_x[cx+1]-1] x [coord_y[cy], coord_y[cy+1]-1] du système de coordonnées original.

Pour chaque cellule compressée, un tableau de sommes de préfixes 2D (cellules_interdites) est utilisé pour déterminer rapidement si la cellule est entièrement recouverte par un obstacle.

2. Algorithme de Dijkstra sur Grille Compressée

Un algorithme de Dijkstra est exécuté sur cette grille compressée pour calculer les temps de trajet minimaux. L'état dans la file de priorité de Dijkstra est (cx, cy, index_coin, distance) :

• (cx, cy) : les indices de la cellule compressée.
• index_coin : représente l'un des quatre coins du rectangle original que représente la cellule compressée (0 pour le coin supérieur gauche (TL), 1 pour le supérieur droit (TR), 2 pour l'inférieur gauche (BL), 3 pour l'inférieur droit (BR)). Cette distinction est cruciale car la distance à un point peut dépendre du coin par lequel on y accède.
• distance : le temps minimal pour atteindre ce coin.

Les transitions dans Dijkstra comprennent :

• Déplacement vers une cellule adjacente (coût 1).
• Déplacement entre les coins d'une même cellule compressée. Par exemple, se déplacer du coin supérieur gauche au coin supérieur droit d'une cellule (cx, cy) coûte (coord_x[cx+1] - coord_x[cx] - 1), qui est la largeur de la cellule moins un. De même pour les déplacements verticaux entre les coins gauche ou droit.

Le point de départ est le coin supérieur gauche de la cellule compressée contenant le point (0,0) dans les coordonnées originales.

3. Résolution de la Question 1 : Temps de Trajet

Pour une requête donnée (qx, qy), nous trouvons d'abord la cellule compressée (ccx, ccy) correspondante. Le temps de trajet minimal pour atteindre (qx, qy) est le minimum des dsitances calculées par Dijkstra pour les quatre coins de (ccx, ccy), ajustées par la distance de Manhattan du coin spécifique au point (qx, qy) à l'intérieur de la cellule. Si le point de requête se trouve dans une cellule bloquée, le résultat est -1.

4. Résolution de la Question 2 : Aire d'Expansion Cumulative

La deuxième question demande le calcul de l'aire totale couverte par l'expansion des chemins à chaque instant t. Ceci est un problème complexe géré efficacement par un algorithme de balayage (sweep-line) :

• Chaque cellule non bloquée (cx, cy), à partir de ses quatre coins, contribue à l'aire totale. Le temps distances[cx][cy][k] indique quand l'expansion atteint le coin k de la cellule (cx, cy).
• L'expansion d'un coin peut être modélisée comme une forme de diamant dont l'aire augmente au fil du temps. Cependant, cette croissance n'est pas linéaire et peut changer de pente lorsque l'expansion rencontre les frontières de la cellule ou les expansions d'autres coins (voisins ou opposés).
• Les moments où la croissance de l'aire change de taux sont calculés pour chaque coin. Ces moments (temps_col_vertical, temps_col_horizontal, temps_col_diagonal) correspondent aux instants où l'onde d'expansion d'un coin "rencontre" celles d'autres coins de la même cellule ou atteint leurs positions logiques.
• Ces points de changement de taux sont transformés en événements pour l'algorithme de balayage. Chaque événement (type_operation, debut_contribution, taux_croissance, temps_evenement) modifie la contribution courante à l'aire totale ou son taux de croissance.
• L'algorithme de balayage trie tous les événements par temps_evenement. Il maintient une aire accumulée (somme_totale_expansion), une valeur d'expansion actuelle (valeur_actuelle_expansion) et un taux de croissance actuel (taux_croissance_expansion). Entre deux événements, l'aire s'accumule selon une progression arithmétique. À chaque événement, valeur_actuelle_expansion et taux_croissance_expansion sont mis à jour en fonction du type_operation.
• La fonction calculer_progression(s, d, longueur) calcule la somme d'une série arithmétique de longueur termes, commençant par s avec une différence commune d.

Cette combinaison de techniques permet de gérer la complexité spatiale et temporelle des deux problèmes de manière efficace.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm> // For std::sort, std::unique, std::lower_bound, std::upper_bound
#include <array> // For std::array

using long_long = long long; // Explicitly use long long

// Fast I/O utilities
char input_buffer[1<<21], *p_buffer1, *p_buffer2;
#define GET_CHAR_FAST() (p_buffer1 == p_buffer2 && (p_buffer2 = (p_buffer1 = input_buffer) + fread(input_buffer, 1, 1 << 21, stdin), p_buffer1 == p_buffer2) ? EOF : *p_buffer1++)

long long read_long() {
    long long value = 0;
    bool negative = false;
    char ch = GET_CHAR_FAST();
    while (ch < '0' || ch > '9') {
        if (ch == '-') negative = true;
        ch = GET_CHAR_FAST();
    }
    while (ch >= '0' && ch <= '9') {
        value = value * 10 + (ch - '0');
        ch = GET_CHAR_FAST();
    }
    return negative ? -value : value;
}

const long_long INF_DISTANCE = 0x3f3f3f3f3f3f3f3fLL; // A large value for infinity

int n_rects, type_probleme, q_queries;
long_long coord_x[1005], nb_coord_x;
long_long coord_y[1005], nb_coord_y;

/*
Mapping des coins pour la cellule compressée (cx, cy):
0: Top-Left (TL)     -> (coord_x[cx], coord_y[cy+1]-1)
1: Top-Right (TR)    -> (coord_x[cx+1]-1, coord_y[cy+1]-1)
2: Bottom-Left (BL)  -> (coord_x[cx], coord_y[cy])
3: Bottom-Right (BR) -> (coord_x[cx+1]-1, coord_y[cy])
*/

struct EtatDijkstra {
    int cx, cy, index_coin;
    long_long distance;
    // Operator for priority queue (min-heap)
    bool operator<(const EtatDijkstra& autre) const {
        return distance > autre.distance;
    }
};

std::priority_queue<EtatDijkstra> dijkstra_priority_queue;
bool visited_dijkstra[1005][1005][4];
long_long distances[1005][1005][4]; // distances[cx][cy][index_coin]
int blocked_cells[1005][1005]; // 2D prefix sum for blocked cells

void execute_dijkstra() {
    for (int i = 0; i <= nb_coord_x; ++i) {
        for (int j = 0; j <= nb_coord_y; ++j) {
            for (int k = 0; k < 4; ++k) {
                distances[i][j][k] = INF_DISTANCE;
                visited_dijkstra[i][j][k] = false;
            }
        }
    }

    // Find the compressed indices for the origin point (0,0)
    int start_cx = std::lower_bound(coord_x + 1, coord_x + nb_coord_x + 1, 0) - coord_x;
    int start_cy = std::lower_bound(coord_y + 1, coord_y + nb_coord_y + 1, 0) - coord_y;

    // Start Dijkstra from the Top-Left (0) corner of the cell containing (0,0)
    dijkstra_priority_queue.push({start_cx, start_cy, 0, distances[start_cx][start_cy][0] = 0});

    while (!dijkstra_priority_queue.empty()) {
        EtatDijkstra current = dijkstra_priority_queue.top();
        dijkstra_priority_queue.pop();

        int cx = current.cx, cy = current.cy, type_coin = current.index_coin;
        if (visited_dijkstra[cx][cy][type_coin]) continue;
        visited_dijkstra[cx][cy][type_coin] = true;

        auto update_distance = [&](int next_cx, int next_cy, int next_type_coin, long_long movement_cost) {
            // Check if the target cell is blocked by an obstacle
            if (next_cx >= 1 && next_cx < nb_coord_x && next_cy >= 1 && next_cy < nb_coord_y &&
                blocked_cells[next_cx][next_cy] == 0 && distances[next_cx][next_cy][next_type_coin] > current.distance + movement_cost) {
                distances[next_cx][next_cy][next_type_coin] = current.distance + movement_cost;
                dijkstra_priority_queue.push({next_cx, next_cy, next_type_coin, distances[next_cx][next_cy][next_type_coin]});
            }
        };

        // Transitions based on current corner (type_coin)
        if (type_coin == 0) { // From Top-Left (TL)
            // Move Left (to TR of cell to the left)
            update_distance(cx - 1, cy, 1, 1);
            // Move Up (to BL of cell above)
            update_distance(cx, cy + 1, 2, 1);
            // Move within cell: TL to TR (horizontal jump)
            update_distance(cx, cy, 1, coord_x[cx + 1] - coord_x[cx] - 1);
            // Move within cell: TL to BL (vertical jump)
            update_distance(cx, cy, 2, coord_y[cy + 1] - coord_y[cy] - 1);
        } else if (type_coin == 1) { // From Top-Right (TR)
            // Move Right (to TL of cell to the right)
            update_distance(cx + 1, cy, 0, 1);
            // Move Up (to BR of cell above)
            update_distance(cx, cy + 1, 3, 1);
            // Move within cell: TR to TL (horizontal jump)
            update_distance(cx, cy, 0, coord_x[cx + 1] - coord_x[cx] - 1);
            // Move within cell: TR to BR (vertical jump)
            update_distance(cx, cy, 3, coord_y[cy + 1] - coord_y[cy] - 1);
        } else if (type_coin == 2) { // From Bottom-Left (BL)
            // Move Left (to BR of cell to the left)
            update_distance(cx - 1, cy, 3, 1);
            // Move Down (to TL of cell below)
            update_distance(cx, cy - 1, 0, 1);
            // Move within cell: BL to BR (horizontal jump)
            update_distance(cx, cy, 3, coord_x[cx + 1] - coord_x[cx] - 1);
            // Move within cell: BL to TL (vertical jump)
            update_distance(cx, cy, 0, coord_y[cy + 1] - coord_y[cy] - 1);
        } else { // type_coin == 3 (From Bottom-Right (BR))
            // Move Right (to BL of cell to the right)
            update_distance(cx + 1, cy, 2, 1);
            // Move Down (to TR of cell below)
            update_distance(cx, cy - 1, 1, 1);
            // Move within cell: BR to BL (horizontal jump)
            update_distance(cx, cy, 2, coord_x[cx + 1] - coord_x[cx] - 1);
            // Move within cell: BR to TR (vertical jump)
            update_distance(cx, cy, 1, coord_y[cy + 1] - coord_y[cy] - 1);
        }
    }
}

// Structure for sweep-line events
struct SweepEvent {
    int type_operation; // 0 for query, 1 for add, -1 for subtract
    long_long initial_val;      // Initial value for arithmetic progression
    long_long slope_change;      // Difference for arithmetic progression (slope)
    long_long event_time; // Time of the event

    // For sorting, queries should be processed after additions/subtractions at the same time
    bool operator<(const SweepEvent& other) const {
        if (event_time == other.event_time) {
            return std::abs(type_operation) > std::abs(other.type_operation); // Queries (type 0) last
        }
        return event_time < other.event_time;
    }
};
std::vector<SweepEvent> event_list;
long_long answers_q2[200005];

// Calculates the sum of an arithmetic progression: s, s+d, s+2d, ..., s+(length-1)d
inline long_long calculate_arithmetic_sum(long_long s, long_long d, long_long length) {
    if (length <= 0) return 0;
    return length * (2 * s + (length - 1) * d) / 2;
}

void solve_q2() {
    // Iterate through all unblocked compressed cells
    for (int cx = 1; cx < nb_coord_x; cx++) {
        for (int cy = 1; cy < nb_coord_y; cy++) {
            if (blocked_cells[cx][cy] > 0) continue; // Cell is blocked

            long_long dim_x_cell = coord_x[cx + 1] - coord_x[cx];
            long_long dim_y_cell = coord_y[cy + 1] - coord_y[cy];
            
            if (dim_x_cell == 1 && dim_y_cell == 1) { // Single unit cell
                if (distances[cx][cy][0] != INF_DISTANCE) { // Assuming TL corner is representative for unit cell start
                    event_list.push_back({1, 1, 0, distances[cx][cy][0]}); // Add 1 area at dist[0]
                    event_list.push_back({-1, 1, 0, distances[cx][cy][0] + 1}); // Remove 1 area at dist[0]+1
                }
                continue;
            }

            // Iterate over all 4 corners (0, 1, 2, 3)
            for (int current_corner_idx = 0; current_corner_idx < 4; current_corner_idx++) {
                long_long d_current = distances[cx][cy][current_corner_idx];
                if (d_current == INF_DISTANCE) continue; // Unreachable corner

                // Calculate collision times with other corners of the same logical cell
                // These formulas derive from when wavefronts (diamonds) starting at different
                // corners and times would "meet" or fully expand into the space of another corner.

                // Collision with vertical neighbor (k_current ^ 2) (e.g., TL vs BL, TR vs BR)
                long_long val_t_vert_dist = dim_y_cell - 2 - std::abs(d_current - distances[cx][cy][current_corner_idx ^ 2]);
                long_long time_col_vertical = (val_t_vert_dist / 2) + (val_t_vert_dist % 2 != 0 ? (current_corner_idx < (current_corner_idx ^ 2)) : 0) + std::max(d_current, distances[cx][cy][current_corner_idx ^ 2]);
                
                // Collision with horizontal neighbor (k_current ^ 1) (e.g., TL vs TR, BL vs BR)
                long_long val_t_horiz_dist = dim_x_cell - 2 - std::abs(d_current - distances[cx][cy][current_corner_idx ^ 1]);
                long_long time_col_horizontal = (val_t_horiz_dist / 2) + (val_t_horiz_dist % 2 != 0 ? (current_corner_idx < (current_corner_idx ^ 1)) : 0) + std::max(d_current, distances[cx][cy][current_corner_idx ^ 1]);
                
                // Collision with diagonal opposite (k_current ^ 3) (e.g., TL vs BR, TR vs BL)
                long_long val_t_diag_dist = dim_x_cell + dim_y_cell - 3 - std::abs(d_current - distances[cx][cy][current_corner_idx ^ 3]);
                long_long time_col_diagonal = (val_t_diag_dist / 2) + (val_t_diag_dist % 2 != 0 ? (current_corner_idx < (current_corner_idx ^ 3)) : 0) + std::max(d_current, distances[cx][cy][current_corner_idx ^ 3]);

                if (time_col_vertical < d_current || time_col_horizontal < d_current) continue; 

                // Ensure t_vertical is always smaller or equal to t_horizontal for simplified processing
                if (time_col_vertical > time_col_horizontal) std::swap(time_col_vertical, time_col_horizontal);

                // Add initial growth from this corner
                event_list.push_back({1, 1, 1, d_current}); // Start: initial area 1, slope +1

                if (time_col_diagonal < time_col_vertical) { // Diagonal collision happens first
                    event_list.push_back({-1, time_col_diagonal + 2 - d_current, -1, time_col_diagonal + 1}); // Stop growth fully
                    continue;
                }
                event_list.push_back({-1, time_col_vertical + 2 - d_current, -1, time_col_vertical + 1}); // Decrease slope by 1
                event_list.push_back({1, time_col_vertical + 1 - d_current, 0, time_col_vertical + 1}); // Reset initial val, slope unchanged (effectively new slope is 0)

                if (time_col_diagonal < time_col_horizontal) { // Diagonal collision happens before second neighbor collision
                    event_list.push_back({-1, time_col_vertical + 1 - d_current, 0, time_col_diagonal + 1}); // Stop growth
                    continue;
                }
                event_list.push_back({-1, time_col_vertical + 1 - d_current, 0, time_col_horizontal + 1}); // Decrease slope by 0 (effective no change, but event needed)
                event_list.push_back({1, time_col_vertical - d_current, -1, time_col_horizontal + 1}); // Decrease slope by 1 (total -2 slope now)
                
                // Final adjustment for diagonal collision, considering the already modified slope
                event_list.push_back({-1, std::max(0LL, time_col_vertical - d_current - (time_col_diagonal - time_col_horizontal)), 1, std::min(time_col_diagonal + 1, time_col_horizontal + 1 + time_col_vertical - d_current)});
            }
        }
    }

    // Sort all events
    std::sort(event_list.begin(), event_list.end());

    long_long current_slope = 0; // k
    long_long current_initial_value = 0; // al
    long_long cumulative_area_sum = 0; // dd
    long_long last_processed_time = 0; // lst

    for (const auto& event : event_list) {
        long_long interval_duration = event.event_time - last_processed_time;
        if (interval_duration > 0) {
            cumulative_area_sum += calculate_arithmetic_sum(current_initial_value, current_slope, interval_duration);
            current_initial_value += current_slope * interval_duration;
        }
        last_processed_time = event.event_time;

        if (event.type_operation == 0) { // Query event
            answers_q2[event.slope_change] = cumulative_area_sum;
        } else if (event.type_operation == 1) { // Add event
            current_initial_value += event.initial_val;
            current_slope += event.slope_change;
            cumulative_area_sum += event.initial_val; // For the current point in time
        } else { // Subtract event (type_operation == -1)
            current_initial_value -= event.initial_val;
            current_slope += event.slope_change; // slope_change is typically -1 or 0 for subtracts
            cumulative_area_sum -= event.initial_val; // For the current point in time
        }
    }
}

std::array<long_long, 4> initial_rectangles[405]; // x1, x2, y1, y2

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    n_rects = read_long();
    type_probleme = read_long();
    q_queries = read_long();

    for (int i = 1; i <= n_rects; i++) {
        long_long& x1 = initial_rectangles[i][0];
        long_long& x2 = initial_rectangles[i][1];
        long_long& y1 = initial_rectangles[i][2];
        long_long& y2 = initial_rectangles[i][3];
        x1 = read_long();
        x2 = read_long();
        y1 = read_long();
        y2 = read_long();

        coord_x[++nb_coord_x] = x1;
        coord_x[++nb_coord_x] = x2 + 1;
        coord_y[++nb_coord_y] = y1;
        coord_y[++nb_coord_y] = y2 + 1;
    }

    // Add reference points (0, 1) and extreme values for coordinate compression
    coord_x[++nb_coord_x] = 0;
    coord_x[++nb_coord_x] = 1;
    coord_x[++nb_coord_x] = -INF_DISTANCE; 
    coord_x[++nb_coord_x] = INF_DISTANCE;
    coord_y[++nb_coord_y] = 0;
    coord_y[++nb_coord_y] = 1;
    coord_y[++nb_coord_y] = -INF_DISTANCE;
    coord_y[++nb_coord_y] = INF_DISTANCE;

    // Sort and unique coordinate arrays
    std::sort(coord_x + 1, coord_x + nb_coord_x + 1);
    nb_coord_x = std::unique(coord_x + 1, coord_x + nb_coord_x + 1) - coord_x - 1;
    std::sort(coord_y + 1, coord_y + nb_coord_y + 1);
    nb_coord_y = std::unique(coord_y + 1, coord_y + nb_coord_y + 1) - coord_y - 1;

    // Build 2D prefix sum for blocked cells
    for (int i = 1; i <= n_rects; i++) {
        long_long x1_orig = initial_rectangles[i][0];
        long_long x2_orig = initial_rectangles[i][1];
        long_long y1_orig = initial_rectangles[i][2];
        long_long y2_orig = initial_rectangles[i][3];

        int cx1 = std::lower_bound(coord_x + 1, coord_x + nb_coord_x + 1, x1_orig) - coord_x;
        int cx2 = std::lower_bound(coord_x + 1, coord_x + nb_coord_x + 1, x2_orig + 1) - coord_x;
        int cy1 = std::lower_bound(coord_y + 1, coord_y + nb_coord_y + 1, y1_orig) - coord_y;
        int cy2 = std::lower_bound(coord_y + 1, coord_y + nb_coord_y + 1, y2_orig + 1) - coord_y;

        // Mark obstacles using difference array for 2D prefix sum
        blocked_cells[cx1][cy1]++;
        blocked_cells[cx2][cy1]--;
        blocked_cells[cx1][cy2]--;
        blocked_cells[cx2][cy2]++;
    }

    // Compute actual blocked status using 2D prefix sum
    for (int i = 1; i <= nb_coord_x; i++) {
        for (int j = 1; j <= nb_coord_y; j++) {
            blocked_cells[i][j] += blocked_cells[i - 1][j] + blocked_cells[i][j - 1] - blocked_cells[i - 1][j - 1];
        }
    }

    execute_dijkstra(); // Precompute distances for all corners

    if (type_probleme == 1) { // Question 1: Point query
        while (q_queries--) {
            long_long qx = read_long();
            long_long qy = read_long();

            // Find the compressed cell containing (qx, qy)
            int query_cx = std::upper_bound(coord_x + 1, coord_x + nb_coord_x + 1, qx) - coord_x - 1;
            int query_cy = std::upper_bound(coord_y + 1, coord_y + nb_coord_y + 1, qy) - coord_y - 1;

            if (query_cx < 1 || query_cx >= nb_coord_x || query_cy < 1 || query_cy >= nb_coord_y ||
                blocked_cells[query_cx][query_cy] > 0) { 
                 std::cout << -1 << "\n";
                 continue;
            }

            long_long min_dist_to_query = INF_DISTANCE;

            // Calculate distance from each of the 4 corners of the cell to (qx, qy)
            // Corners: TL (0), TR (1), BL (2), BR (3)
            // Manhattan distances from corner to (qx,qy) in original coordinates
            
            // From TL (0)
            if (distances[query_cx][query_cy][0] != INF_DISTANCE)
                min_dist_to_query = std::min(min_dist_to_query, distances[query_cx][query_cy][0] + (qx - coord_x[query_cx]) + (coord_y[query_cy + 1] - 1 - qy));
            
            // From TR (1)
            if (distances[query_cx][query_cy][1] != INF_DISTANCE)
                min_dist_to_query = std::min(min_dist_to_query, distances[query_cx][query_cy][1] + (coord_x[query_cx + 1] - 1 - qx) + (coord_y[query_cy + 1] - 1 - qy));
            
            // From BL (2)
            if (distances[query_cx][query_cy][2] != INF_DISTANCE)
                min_dist_to_query = std::min(min_dist_to_query, distances[query_cx][query_cy][2] + (qx - coord_x[query_cx]) + (qy - coord_y[query_cy]));
            
            // From BR (3)
            if (distances[query_cx][query_cy][3] != INF_DISTANCE)
                min_dist_to_query = std::min(min_dist_to_query, distances[query_cx][query_cy][3] + (coord_x[query_cx + 1] - 1 - qx) + (qy - coord_y[query_cy]));
            
            std::cout << (min_dist_to_query >= INF_DISTANCE ? -1 : min_dist_to_query) << "\n";
        }
    } else { // Question 2: Cumulative area query
        for (int i = 1; i <= q_queries; i++) {
            event_list.push_back({0, 0, i, read_long()}); // Add queries as events, slope_change stores query index
        }
        solve_q2(); // Execute sweep-line
        for (int i = 1; i <= q_queries; i++) {
            std::cout << answers_q2[i] << "\n";
        }
    }

    return 0;
}