输入描述:

单个测试点中包含多组数据。
输入的第一行为一个非负整数 T，表示数据的组数。
接下来依次描述每组数据，对于每组数据：
• 第一行 2 个非负整数 n, m，分别表示节点数、边数。
• 接下来 m 行，每行 4 个正整数 u, v, l, a，描述一条连接节点 u, v 的、长度为 l、海
拔为 a 的边。
– 在这里，我们保证 1 ≤ u, v ≤ n。
• 接下来一行 3 个非负数 Q, K, S，其中 Q 表示总天数，K ∈ {0, 1} 是一个会在下面
被用到的系数，S 表示的是可能的最高水位线。
• 接下来 Q 行依次描述每天的状况。每行 2 个整数 v0, p0 描述一天：
– 这一天的出发节点为 v = (v0 + K × lastans − 1) mod n + 1。
– 这一天的水位线为 p = (p0 + K × lastans) mod (S + 1)。
– 其中 lastans 表示上一天的答案（最小步行总路程）。特别地，我们规定第 1
天时 lastans = 0。
– 在这里，我们保证 1 ≤ v0 ≤ n，0 ≤ p0 ≤ 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

第一天没有降水，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) mod 5 + 1 = 5，p = (2 + 0) mod
(3 + 1) = 2。
第二天的答案是 2，因此第三天的 v = (2 + 2 − 1) mod 5 + 1 = 4，p = (0 + 2) mod
(3 + 1) = 2。
第三天的答案是 3，因此第四天的 v = (4 + 3 − 1) mod 5 + 1 = 2，p = (0 + 3) mod
(3 + 1) = 3。

备注:

所有测试点均保证 T ≤ 3，所有测试点中的所有数据均满足如下限制：
 • n ≤ 2 × 105，m ≤ 4 × 105，Q ≤ 4 × 105，K ∈ {0, 1}，1 ≤ S ≤ 109。
 • 对于所有边：l ≤ 104，a ≤ 109。• 任意两点之间都直接或间接通过边相连。
 为了方便你快速理解， 我们在表格中使用了一些简单易懂的表述 在. 此，我们对这些内容作形式化的说明：. 
• 图形态：对于表格中该项为“一棵树”或“一条链”的测试点，保证 m = n − 1。 
除此之外，这两类测试点分别满足如下限制： 
– 一棵树：保证输入的图是一棵树，即保证边不会构成回路。 
– 一条链：保证所有边满足 u + 1 = v。 
• 海拔：对于表格中该项为“一种”的测试点，保证对于所有边有 a = 1。 
• 强制在线：对于表格中该项为“是”的测试点，保证 K = 1；如果该项为“否”，则有 K = 0。 
• 对于所有测试点，如果上述对应项为“不保证”，则对该项内容不作任何保证。