题目描述

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.

5 10
1 2 13
1 3 13
1 4 12
4 5 11
4 4 7
4 2 10
4 5 13
1 4 8
2 4 8
3 4 8
5
4 4
2 4
28 29
10 10
1 5

0
24
11
0
92