魔力之都

题目描述

本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。

魔力之都可以抽象成一个$n$个节点、$m$条边的无向连通图（节点的编号从$1$至$n$）。我们依次用$l$，$a$描述一条边的长度、海拔。

作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。

我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。

$Yazid$是一名来自魔力之都的$Oler$，刚参加完$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 lastans - 1) \bmod n + 1$。
  • 这一天的水位线为$p = (p_{0} + K \times lastans) \bmod (S + 1)$。
  • 其中$lastans$表示上一天的答案（最小步行总路程）。特别地，我们规定第$1$天时$lastans = 0$。
  • 在这里，我们保证$1 \leq v_{0} \leq n$，$0 \leq p_{0} \leq S$。

对于输入中的每一行，如果该行包含多个数，则用单个空格将它们隔开。

输出格式

依次输出各组数据的答案。对于每组数据：

• 输出$Q$行每行一个整数，依次表示每天的最小步行总路程。

数据范围与提示

所有测试点均保证$T \leq 3$，所有测试点中的所有数据均满足如下限制：

• $n \leq 2 \times 10^{5}$，$m \leq 4 \times 10^{5}$，$Q \leq 4 \times 10^{5}$，$K \in \{0,1\}$，$1 \leq S \leq 10^{9}$。
• 对于所有边：$l \leq 10^{4}$，$a \leq 10^{9}$。
• 任意两点之间都直接或间接通过边相连。

为了方便你快速理解，我们在表格中使用了一些简单易懂的表述。在此，我们对这些内容作形式化的说明：

• 图形态：对于表格中该项为"一棵树"或"一条链"的测试点，保证$m = n - 1$。除此之外，这两类测试点分别满足如下限制：
  1. 一棵树：保证输入的图是一棵树，即保证边不会构成回路。
  2. 一条链：保证所有边满足$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$	一条链	不保证
			$8$
			$9$
$\leq 200000$		$100000$	$10$	一棵树
			$11$			是
	$\leq 400000$		$12$	不保证		否
			$13$
			$14$
$\leq 1500$	$\leq 4000$	$2000$	$15$			是
			$16$
$\leq 200000$	$\leq 400000$	$100000$	$17$
			$18$
		$400000$	$19$
			$20$

为了优化你的阅读体验，我们在表格中把测试点的编号放在了中间，请注意这一点。

样例

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

说明

第一天没有降水，$Yazid$可以坐车直接回到家中。

第二天、第三天、第四天的积水情况相同，均为连接$1$，$2$号节点的边、连接$3$，$4$号点的边有积水。

对于第二天，$Yazid$从$2$号点出发坐车只能去往$3$号节点，对回家没有帮助。因此$Yazid$只能纯靠徒步回家。

对于第三天，从$4$号节点出发的唯一一条边是有积水的，车也就变得无用了。$Yazid$只能纯靠徒步回家。

对于第四天，$Yazid$可以坐车先到达$2$号节点，再步行回家。

第五天所有的边都积水了，因此$Yazid$只能纯靠徒步回家。

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

说明

本组数据强制在线。

第一天的答案是$0$，因此第二天的$v=(5+0-1)\bmod 5+1=5$，$p=(2+0)\bmod (3+1)=2$。

第二天的答案是$2$，因此第三天的$v=(2+2-1)\bmod 5+1=4$，$p=(0+2)\bmod (3+1)=2$。

第三天的答案是$3$，因此第四天的$v=(4+3-1)\bmod 5+1=2$，$p=(0+3)\bmod (3+1)=3$。

见return3.in

见return3.ans

见return4.in

见return4.ans

见return5.in

见return5.ans