题目描述

计划建设一张由 $n$ 个地铁站和 $m$ 条候选隧道组成的网络。每条隧道连接两个站，并有一个整数建设费用。

最终只会建设部分隧道。由于政策限制，只允许建设费用位于区间 $[L,H]$ 内的隧道。

对于给定的 $L,H$，需要从所有允许的隧道中选择一组进行建设，并按以下优先级优化：

1. 首先，使能够互相连通的车站对数量最大；
2. 在满足第一条的所有方案中，使建设总费用最小。

如果允许的边能够使整个图连通，那么这等价于求允许边子图的最小生成树；若不能连通，则需要得到使各连通块内部尽可能连通、且总费用最小的最优生成森林。

你需要回答很多组不同的 $[L,H]$。

输入格式

第一行三个整数 $n,m,f$：

• $2\le n\le20000$；
• $1\le m\le100000$；
• $f\in\{0,1\}$，表示查询是否经过在线编码。

接下来 $m$ 行，每行三个整数 $x,y,w$，表示一条连接 $x,y$ 的候选隧道，费用为 $w$：

• $1\le x\ne y\le n$；
• $1\le w\le10^6$。

允许多条隧道连接同一对车站。

接下来一行一个整数 $q$，$1\le q\le10^6$。

之后 $q$ 行给出查询。

当 $f=0$

每行直接给出 $L_i,H_i$。

当 $f=1$

输入中给出的不是实际的 $(L_i,H_i)$，而是：

$(L_i+A_{i-1},\ H_i+A_{i-1})$，

其中 $A_{i-1}$ 是上一次查询的答案，且 $A_0=0$。

解码后的查询保证满足 $1\le L_i\le H_i\le10^6$。

输出格式

对于每个查询输出一行，表示满足上述优化目标时的最小总建设费用。

样例 1

5 7 0
1 2 2
2 3 4
3 4 3
4 5 1
5 1 3
2 5 4
1 4 5
5
1 2
1 4
2 3
3 5
4 5

3
9
8
14
13

样例 2

5 7 1
1 2 2
2 3 4
3 4 3
4 5 1
5 1 3
2 5 4
1 4 5
5
1 2
4 7
11 12
11 13
18 19

3
9
8
14
13

两个样例表示同一串真实查询，第二个样例使用上一问答案进行了编码。

子任务

设 $W$ 为该子任务中出现的最大边权。