题目描述

G 省的高速公路系统可以看作一个包含 $n$ 个节点和 $m$ 条边的带权无向图。每条边代表一段高速公路，每个节点代表一座城市。所有高速公路段均为双向通行。第 $i$ 段高速公路连接两座城市 $u_i$ 与 $v_i$，长度为 $w_i$ 公里。

Orange 小姐 目前正在 G 省通勤。她的汽车每行驶一公里消耗一单位燃油。任意城市均设有加油站，可以在此将汽车的油箱加满，且 Orange 小姐 的汽车在城市内部行驶时的燃油消耗可忽略不计。Orange 小姐 规划了 $q$ 次出行。第 $i$ 次出行从城市 $x$ 出发，目的地为城市 $y$。她希望知道完成此次出行所需的最小油箱容量。

然而，她尚未确定具体的 $x$ 与 $y$，仅知晓 $x$ 与 $y$ 落在区间 $[l_i, r_i]$ 内。具体而言，对于所有满足 $l_i \le x < y \le r_i$ 的 $x$ 与 $y$，Orange 小姐希望求得从 $x$ 出发前往 $y$ 所需的最小油箱容量之和。形式化地，记 $f(x, y)$ 为从 $x$ 出发到达 $y$ 的行程所需的最小油箱容量。你需要输出 $\sum\limits_{l_i \le x < y \le r_i} f(x, y)$ 的值。

由于她需要依据当前的计划来考虑下一步安排，本题将对查询参数施加一定的加密约束。

输入格式

第一行包含两个整数 $n$（$1\leq n \leq 5 \times 10^{4}$）和 $m$（$1 \leq m \leq 2 \times 10^{5}$）。

接下来的 $m$ 行，每行包含三个整数 $u, v$（$1\leq u,v\leq n$）和 $w$（$1\leq w \leq 10^{9}$），表示连接 $u$ 与 $v$、权值为 $w$ 的一条边。保证图是连通的。

随后一行包含一个整数 $q$（$1\leq q \leq 5 \times 10^{4}$）。

接下来的 $q$ 行，每行包含两个整数 $l', r'$（$0\leq l',r'\leq 10^{18}$），表示加密后的查询。每次你需要将当前的 $l'$ 和 $r'$ 分别与上一次的答案进行按位异或运算，以得到真实的 $l$ 与 $r$。数据保证真实的 $l$ 与 $r$ 满足 $1 \leq l \leq r \leq n$。

输出格式

输出 $q$ 行，每行一个整数，表示对应查询的答案。

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

提示

翻译由 DeepSeek V3.2 完成