Problem Description

This problem is set in the magical city, where we will introduce some necessary settings.

The magical city can be abstracted as an undirected connected graph with $n$ nodes and $m$ edges (node numbering from $1$ to $n$). We use $l$ and $a$ to describe the length and altitude of an edge, respectively.

As a representative city of monsoon climate, the magical city is often accompanied by rain, leading to inevitable road flooding. The flooded edges are always the ones with the lowest relative altitude. We use the water level to describe the degree of rainfall, which means: all edges with an altitude not exceeding the water level are flooded.

Yazid, an OIer from the magical city, has just finished ION2018 and is about to embark on his return journey to his warm home. Yazid's home is exactly at node $1$ in the magical city. For the next $Q$ days, each day Yazid will tell you his starting point $v$ and the water level $p$ for that day.

Each day, Yazid starts with a car at his starting point. This car, due to some faults, cannot pass through flooded edges. Yazid can get off the car at any node, after which he can walk through flooded edges. However, the car will be left at the node where he gets off and will not be used again. It is important to note that the car resets the next day, meaning:
- The car will be ready at the new starting point.
- Yazid cannot use a car parked at a previous location.

Yazid dislikes walking in the rain, so he hopes to minimize the total length of edges he walks through while achieving his goal of returning home. Please help Yazid calculate this.

Some test cases will enforce online processing, details of which can be found in the Input Format and Subtasks.

Input Format

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

Each dataset is described as follows:

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

The next $m$ lines each contain four positive integers $u, v, l, a$, describing an edge connecting nodes $u$ and $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 possible maximum water level.

The next $Q$ lines describe the conditions for each day. Each line contains two integers $v_0, p_0$:
- The starting node for that day is $v = (v_0 + K \times \text{lastans} - 1) \bmod n + 1$.
- The water level for that day is $p = (p_0 + K \times \text{lastans}) \bmod (S + 1)$.

Here, $\text{lastans}$ denotes the answer (minimum walking distance) from the previous day. Specifically, we set $\text{lastans} = 0$ for the first day. We guarantee $1 \leq v_0 \leq n$ and $0 \leq p_0 \leq S$.

For each line in the input containing multiple numbers, they are separated by a single space.

Output Format

Output the answers for each dataset sequentially. For each dataset:

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

Sample Input and Output

Input Example #1

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

Output Example #1

0
50
200
50
150

Input Example #2

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

Output Example #2

0
2
3
1

Notes/Hints

More Examples

More examples can be found in the attached files.

Example 3

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

This example satisfies a single altitude and is not enforced online.

Example 4

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

This example satisfies a chain graph structure and is enforced online.

Example 5

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

This example is not enforced online.

Example 1 Explanation

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

On the second, third, and fourth days, the flooding is the same, affecting the edges connecting nodes 1 and 2, and nodes 3 and 4.

For the second day, Yazid starting from node 2 can only drive to node 3, which is not helpful for returning home. Therefore, Yazid must walk home.

For the third day, the only edge starting from node 4 is flooded, making the car useless. Yazid must walk home.

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

On the fifth day, all edges are flooded, so Yazid must walk home.

Example 2 Explanation

This dataset is enforced online.

The answer for the first day is $0$, so for the second day, $v = (5 + 0 - 1) \bmod 5 + 1 = 5$, $p = (2 + 0) \bmod (3 + 1) = 2$.

The answer for the second day is $2$, so for the third day, $v = (2 + 2 - 1) \bmod 5 + 1 = 4$, $p = (0 + 2) \bmod (3 + 1) = 2$.

The answer for the third day is $3$, so for the fourth day, $v = (4 + 3 - 1) \bmod 5 + 1 = 2$, $p = (0 + 3) \bmod (3 + 1) = 3$.

Data Range and Constraints

All test cases guarantee $T \leq 3$, and all data within the test cases satisfy the following constraints:

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

For your quick understanding, we have used some straightforward expressions in the table. Here, we provide formal descriptions of these contents:

• Graph Structure: For test points where this is "a tree" or "a chain", we guarantee $m = n - 1$. Additionally, these test points are subject to the following constraints:
• A Tree: The input graph is guaranteed to be a tree, meaning no cycles are formed by the edges.
• A Chain: All edges satisfy $u + 1 = v$.
• Altitude: For test points where this is "one type", we guarantee $a = 1$ for all edges.
• Enforced Online: For test points where this is "yes", we guarantee $K = 1$; if this is "no", then $K = 0$.
• For all test points, if the corresponding item is "not guaranteed", no guarantees are made for that item.

见题面 Input 部分

见题面 Output 部分