Problem Description

The story of this problem takes place in the City of Magic. Here we introduce some necessary settings.

The City of Magic can be abstracted as a connected undirected graph with $n$ nodes and $m$ edges (the nodes are numbered from $1$ to $n$). For each edge, we use $l, a$ to describe its length and altitude.

As a typical monsoon-climate city, the City of Magic often has rain, so water on roads is unavoidable. Since the drainage system of the whole city is connected, the flooded edges must be those with relatively low altitude. We use the water level to describe the amount of rain. Its meaning is: all edges whose altitude is not greater than the water level are flooded.

Yazid is an OIer from the City of Magic. After just finishing ION2018, he is going to start his return journey to his warm home. Yazid’s home happens to be at node $1$ of the City of Magic. For the next $Q$ days, each day Yazid will tell you his starting point $v$ and the water level $p$ of that day.

Each day, Yazid has a car at the starting point. Because of some malfunctions, this car cannot pass through flooded edges. Yazid may get out of the car at any node; after that he can walk through flooded edges. However, the car will be left at the node where he gets out and will not be used again. Note in particular that the car will be reset on the next day, which means:

• The car will be prepared at the new starting point.
• Yazid cannot use a car parked somewhere previously.

Yazid really dislikes walking on rainy days, so while still getting home, he wants to minimize the total length of the edges he walks through. Please help Yazid compute this.

Some test points of this problem are forced online. For details, see Input Format and Subtasks.

Input Format

A single test file contains multiple test cases. The first line is a non-negative integer $T$, indicating the number of test cases.

Then each test case is described as follows:

The first line contains two non-negative integers $n, m$, representing the number of nodes and edges.

The next $m$ lines each contain four positive integers $u, v, l, a$, describing an edge connecting nodes $u, v$ with length $l$ and altitude $a$. Here we guarantee $1 \leq u,v \leq n$.

The next line contains three non-negative integers $Q, K, S$, where $Q$ is the total number of days, $K \in {0,1}$ is a coefficient used below, and $S$ is the maximum possible water level.

The next $Q$ lines describe the situation for each day. Each line contains two integers $v_0, p_0$:

• The starting node is $v = (v_0 + K \times \mathrm{lastans} - 1) \bmod n + 1$.
• The water level is $p = (p_0 + K \times \mathrm{lastans}) \bmod (S + 1)$.

Here $\mathrm{lastans}$ is the answer of the previous day (the minimum total walking distance). In particular, we define $\mathrm{lastans} = 0$ on day $1$. We guarantee $1 \leq v_0 \leq n$, $0 \leq p_0 \leq S$.

For each line of the input, if it contains multiple numbers, they are separated by a single space.

Output Format

Output the answers for each test case in order. For each test case:

• Output $Q$ lines, each containing one integer, representing the minimum total walking distance for each day.

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

Hint

More Samples

More samples can be downloaded from the additional files.

Sample 3

See return3.in and return3.ans in the additional files.

This sample satisfies that there is only one altitude value, and it is not forced online.

Sample 4

See return4.in and return4.ans in the additional files.

This sample satisfies that the graph is a chain, and it is forced online.

Sample 5

See return5.in and return5.ans in the additional files.

This sample is not forced online.

Explanation of Sample 1

On the first day there is no rainfall, so Yazid can drive directly home.

On the second, third, and fourth days, the flooded situation is the same: the edge connecting nodes 1 and 2, and the edge connecting nodes 3 and 4 are flooded.

On the second day, Yazid starts from node 2. By car he can only go to node 3, which does not help him get home. Therefore, Yazid can only walk all the way home.

On the third day, the only edge from node 4 is flooded, so the car becomes useless. Yazid can only walk all the way home.

On the fourth day, Yazid can drive to node 2 first, then walk home.

On the fifth day, all edges are flooded, so Yazid can only walk all the way home.

Explanation of Sample 2

This test case is forced online.

The answer on day 1 is $0$, so on day 2, $v=\left( 5+0-1\right)\bmod 5+1=5$, $p=\left(2+0\right)\bmod\left(3+1\right)=2$.

The answer on day 2 is $2$, so on day 3, $v=\left( 2+2-1\right)\bmod 5+1=4$, $p=\left(0+2\right)\bmod\left(3+1\right)=2$.

The answer on day 3 is $3$, so on day 4, $v=\left( 4+3-1\right)\bmod 5+1=2$, $p=\left(0+3\right)\bmod\left(3+1\right)=3$.

Constraints and Conventions

All test points guarantee $T\leq 3$. All data in all test points satisfy the following limits:

• $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$.
• For all edges: $l\leq 10^4$, $a\leq 10^9$.
• Any two nodes are connected directly or indirectly by edges.

To help you understand quickly, we use some easy expressions in the table. Here we give formal explanations:

• Graph shape: for test points where this item is “a tree” or “a chain”, it is guaranteed that $m = n-1$. In addition, these two types satisfy:
  • A tree: the input graph is a tree, i.e. edges do not form cycles.
  • A chain: all edges satisfy $u + 1 = v$.
• Altitude: for test points where this item is “one value”, it is guaranteed that for all edges $a = 1$.
• Forced online: for test points where this item is “yes”, it is guaranteed that $K = 1$; if it is “no”, then $K = 0$.
• For all test points, if the corresponding item is “not guaranteed”, then no guarantee is made for that item.

Translated by ChatGPT 5