P16609 [SYSUCPC 2025] Road2

The highway system of Province G can be viewed as a weighted undirected graph with $n$ nodes and $m$ edges. Each edge represents a segment of the highway, and each node represents a city. Every highway segment is bidirectional. The $i$-th highway segment connects the two cities $u_i$ and $v_i$, with a length of $w_i$ kilometers. $\texttt{Miss Orange}$ is currently commuting in Province G. Her car consumes one unit of fuel per kilometer traveled. Any city has a gas station where the car's fuel tank can be fully refilled, and the fuel consumption of $\texttt{Miss Orange}$'s car while driving within the city is negligible. $\texttt{Miss Orange}$ has planned $q$ trips. The $i$-th trip starts from city $x$ and ends at city $y$. She wants to know the minimum fuel tank capacity required for this trip. However, she has not decided on $x$ and $y$ but only knows that $x$ and $y$ lie within the interval $[l_i, r_i]$. Specifically, for all $l_i \le x < y \le r_i$, Miss Orange wants to know the sum of the minimum fuel tank capacities required to travel from $x$ to $y$. Formally, let $f(x, y)$ denote the fuel tank capacity required for a trip starting at $x$ and ending at $y$. You need to output $\sum\limits_{l_i \le x < y \le r_i} f(x, y)$. Since she needs to consider her next plan based on the current one, certain constraints will be imposed on you in the problem.

The first line contains two integers $n(1\leq n \leq 5 \times 10^{4})$ and $m(1 \leq m \leq 2 \times 10^{5})$. The next $m$ lines each contain three integers $u,v(1\leq u,v\leq n),w(1\leq w \leq 10^{9})$, representing an edge between $u$ and $v$ with a weight of $w$. It is guaranteed that the graph is connected. Then, one line contains an integer $q(1\leq q \leq 5 \times 10^4)$. The next $q$ lines each contain two integers $l',r'(0\leq l',r'\leq 10^{18})$, representing the encrypted queries. Each time, you need to XOR the current $l'$ and $r'$ with the previous answer to obtain the real $l$ and $r$.The data guarantees that the real $l$ and $r$ satisfy $1 \leq l \leq r \leq n$.

Output $q$ lines, each containing one integer representing the answer.