[NOI2018] 归程

本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。 魔力之都可以抽象成一个 $n$ 个节点、$m$ 条边的无向连通图（节点的编号从 $1$ 至 $n$）。我们依次用 $l,a$ 描述一条边的**长度、海拔**。 作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此**有积水的边一定是海拔相对最低的一些边**。我们用**水位线**来描述降雨的程度，它的意义是：所有海拔**不超过**水位线的边都是**有积水**的。 Yazid 是一名来自魔力之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他温暖的家。Yazid 的家恰好在魔力之都的 $1$ 号节点。对于接下来 $Q$ 天，每一天 Yazid 都会告诉你他的出发点 $v$ ，以及当天的水位线 $p$。 每一天，Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。 需要特殊说明的是，第二天车会被重置，这意味着： - 车会在新的出发点被准备好。 - Yazid 不能利用之前在某处停放的车。 Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他**步行经过的边**的总长度。请你帮助 Yazid 进行计算。 本题的部分测试点将强制在线，具体细节请见【输入格式】和【子任务】。

单个测试点中包含多组数据。输入的第一行为一个非负整数 $T$，表示数据的组数。 接下来依次描述每组数据，对于每组数据： 第一行 $2$ 个非负整数 $n,m$，分别表示节点数、边数。 接下来 $m$ 行，每行 $4$ 个正整数 $u, v, l, a$，描述一条连接节点 $u, v$ 的、长度为 $l$、海拔为 $a$ 的边。 在这里，我们保证 $1 \leq u,v \leq n$。 接下来一行 $3$ 个非负数 $Q, K, S$ ，其中 $Q$ 表示总天数，$K \in {0,1}$ 是一个会在下面被用到的系数，$S$ 表示的是可能的最高水位线。 接下来 $Q$ 行依次描述每天的状况。每行 $2$ 个整数 $v_0, p_0$ 描述一天： - 这一天的出发节点为 $v = (v_0 + K \times \mathrm{lastans} - 1) \bmod n + 1$。 - 这一天的水位线为 $p = (p_0 + K \times \mathrm{lastans}) \bmod (S + 1)$。 其中 $\mathrm{lastans}$ 表示上一天的答案（最小步行总路程）。特别地，我们规定第 $1$ 天时 $\mathrm{lastans} = 0$。 在这里，我们保证 $1 \leq v_0 \leq n$，$0 \leq p_0 \leq S$。 对于输入中的每一行，如果该行包含多个数，则用单个空格将它们隔开。

依次输出各组数据的答案。对于每组数据： - 输出 $Q$ 行每行一个整数，依次表示每天的最小步行总路程。

1
4 3
1 2 50 1
2 3 100 2
3 4 50 1
5 0 2
3 0
2 1
4 1
3 1
3 2

0
50
200
50
150

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

0
2
3
1

### 更多样例 更多样例请在附加文件中下载。 #### 样例 3 见附加文件中的 `return3.in` 与 `return3.ans`。 该样例满足海拔为一种，且不强制在线。 #### 样例 4 见附加文件中的 `return4.in` 与 `return4.ans`。 该样例满足图形态为一条链，且强制在线。 #### 样例 5 见附加文件中的 `return5.in` 与 `return5.ans`。 该样例满足不强制在线。 ### 样例 1 解释 第一天没有降水，Yazid 可以坐车直接回到家中。 第二天、第三天、第四天的积水情况相同，均为连接 1，2 号节点的边、连接 3，4 号点的边有积水。 对于第二天，Yazid 从 2 号点出发坐车只能去往 3 号节点，对回家没有帮助。因此 Yazid 只能纯靠徒步回家。 对于第三天，从 4 号节点出发的唯一一条边是有积水的，车也就变得无用了。Yazid 只能纯靠徒步回家。 对于第四天，Yazid 可以坐车先到达 2 号节点，再步行回家。 第五天所有的边都积水了，因此 Yazid 只能纯靠徒步回家。 ### 样例 2 解释 本组数据强制在线。 第一天的答案是 $0$，因此第二天的 $v=\left( 5+0-1\right)\bmod 5+1=5$，$p=\left(2+0\right)\bmod\left(3+1\right)=2$。 第二天的答案是 $2$，因此第三天的 $v=\left( 2+2-1\right)\bmod 5+1=4$，$p=\left(0+2\right)\bmod\left(3+1\right)=2$。 第三天的答案是 $3$，因此第四天的 $v=\left( 4+3-1\right)\bmod 5+1=2$，$p=\left(0+3\right)\bmod\left(3+1\right)=3$。 ### 数据范围与约定 所有测试点均保证 $T\leq 3$，所有测试点中的所有数据均满足如下限制： - $n\leq 2\times 10^5$，$m\leq 4\times 10^5$，$Q\leq 4\times 10^5$，$K\in\left\{0,1\right\}$，$1\leq S\leq 10^9$。 - 对于所有边：$l\leq 10^4$，$a\leq 10^9$。 - 任意两点之间都直接或间接通过边相连。 **为了方便你快速理解，我们在表格中使用了一些简单易懂的表述。在此，我们对这些内容作形式化的说明：** - 图形态：对于表格中该项为 “一棵树” 或 “一条链” 的测试点，保证 $m = n-1$。除此之外，这两类测试点分别满足如下限制： - 一棵树：保证输入的图是一棵树，即保证边不会构成回路。 - 一条链：保证所有边满足 $u + 1 = v$。 - 海拔：对于表格中该项为 “一种” 的测试点，保证对于所有边有 $a = 1$。 - 强制在线：对于表格中该项为 “是” 的测试点，保证 $K = 1$；如果该项为 “否”，则有 $K = 0$。 - 对于所有测试点，如果上述对应项为 “不保证”，则对该项内容不作任何保证。 $n$|$m$|$Q=$|测试点|形态|海拔|强制在线 -|-|-|-|-|-|- $\leq 1$|$\leq 0$|$0$|1|不保证|一种|否 $\leq 6$|$\leq 10$|$10$|2|不保证|一种|否 $\leq 50$|$\leq 150$|$100$|3|不保证|一种|否 $\leq 100$|$\leq 300$|$200$|4|不保证|一种|否 $\leq 1500$|$\leq 4000$|$2000$|5|不保证|一种|否 $\leq 200000$|$\leq 400000$|$100000$|6|不保证|一种|否 $\leq 1500$|$=n-1$|$2000$|7|一条链|不保证|否 $\leq 1500$|$=n-1$|$2000$|8|一条链|不保证|否 $\leq 1500$|$=n-1$|$2000$|9|一条链|不保证|否 $\leq 200000$|$=n-1$|$100000$|10|一棵树|不保证|否 $\leq 200000$|$=n-1$|$100000$|11|一棵树|不保证|是 $\leq 200000$|$\leq 400000$|$100000$|12|不保证|不保证|否 $\leq 200000$|$\leq 400000$|$100000$|13|不保证|不保证|否 $\leq 200000$|$\leq 400000$|$100000$|14|不保证|不保证|否 $\leq 1500$|$\leq 4000$|$2000$|15|不保证|不保证|是 $\leq 1500$|$\leq 4000$|$2000$|16|不保证|不保证|是 $\leq 200000$|$\leq 400000$|$100000$|17|不保证|不保证|是 $\leq 200000$|$\leq 400000$|$100000$|18|不保证|不保证|是 $\leq 200000$|$\leq 400000$|$400000$|19|不保证|不保证|是 $\leq 200000$|$\leq 400000$|$400000$|20|不保证|不保证|是