M. Road2
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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.

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 Miss Orange's car while driving within the city is negligible. 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 \lt 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 \lt 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.

Input

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

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

Example
Input
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
Output
0
24
11
0
92