本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。魔力之都可以抽象成一个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≤u,v≤n。 接下来一行3个非负数 Q, K, S ，其中Q表示总天数，K∈0,1 是一个会在下面被用到的系数，S表示的是可能的最高水位线。 接下来Q行依次描述每天的状况。每行2个整数 v0，p0描述一天： 这一天的出发节点为v=(v_0+K×lastans-1)mod n+1。 这一天的水位线为p=(p_0+K×lastans)mod(S+1)。 其中lastans表示上一天的答案（最小步行总路程）。特别地，我们规定第1天时lastans = 0。在这里，我们保证1≤v_0 ≤n,0≤p_0≤S 。 对于输入中的每一行，如果该行包含多个数，则用单个空格将它们隔开。

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

更多样例 更多样例请在附加文件中下载。 样例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=(5+0-1)mod5+1=5，p=(2+0)mod(3+1)=2。 第二天的答案是 2，因此第三天的v=(2+2-1)mod5+1=4， p=(0+2)mod(3+1)=2。 第三天的答案是 3，因此第四天的 v=(4+3-1)mod5+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。 对于所有测试点，如果上述对应项为“不保证”，则对该项内容不作任何保证。 figure class="image">

NOI国赛