勿忘我

题目描述

宇宙虽有其起源，却没有终结——无限。

星球虽也有起源，却因其自身的力量而逐渐消亡——有限。

拥有智慧之人往往是最为愚蠢者，纵观历史便可得知这一点。

这也可以说是神给那些抵抗者们的——

最后通牒。

俯瞰身底无数的世界线，两条不同的世界线之间也许可以相互到达，但存在一个差异值。

但你并不想记住如此大量繁多的信息，事实上，大部分的信息你都不需要。最终，你选定了 $n$ 条世界线，并找到了其相互之间的 联系 $v$。在此基础之上，你想仅保存少量的世界线间的关系，但是有一些要求：

• $n$ 条世界线间可以通过这些保存的 联系 相互到达，且路径数唯一。
• 不能存在差异值 $< L$ 的 联系，否则会出现负荷领域的既视感。
• 不能存在差异值 $> R$ 的 联系，否则将难以摆脱世界线的收束。
• 除此之外，你还希望差异值之和尽量小。

一句话题意：$n$ 个点，$m$ 条边，询问满足所有边权 $\in [L,R]$ 的最小生成森林，强制在线。

输入格式

第一行两个正整数 $n,m$，分别表示点数和边数。

接下去 $m$ 行，每行三个正整数 $x,y,z$，描述了一条边，连接 $x,y$，边权为 $z$。

然后一行一个正整数 $q$，表示询问次数。

接下去 $q$ 行，每行两个数 $L',R'$，记上一次询问输出的答案为 $lastens$，则 $L=\max(L'-lastens,1),R=R'-lastens$。特殊的，第一次询问时 $lastens$ 为 $0$。

输出格式

对于每次询问，输出一行一个正整数，表示其符合条件的最小生成森林的边权和，如果不存在则输出 $0$。

样例

Input 1

4 7
3 4 6
1 3 9
2 1 2
3 2 9
4 1 4
3 1 5
4 3 5
4
1 10
14 17
11 19
13 14

Output 1

11
9
11
2

Input 2

3 3
3 1 3
3 1 3
3 2 4
7
9 9
3 4
10 11
13 13
5 7
4 10
7 8

Output 2

0
7
7
0
0
4
7

提示说明

对于前 $0\%$ 的数据，是样例。

对于前 $20\%$ 的数据，保证 $n,m,q\le 10^3$。

对于前 $30\%$ 的数据，保证 $n,m,q\le 10^4$。

对于另外 $30\%$ 的数据，保证 $n,m,q\le 10^5$，且数据随机。

对于 $100\%$ 的数据，保证 $n,m,q\le 5\times 10^5,v\le 10^6,L',R'\le 10^9$。