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

The City of Magic can be abstracted as an undirected connected graph with $n$ nodes and $m$ edges (nodes are numbered from $1$ to $n$). We denote the length and altitude of an edge as $l$ and $a$, respectively.

As a city representing a monsoon climate, the City of Magic is often accompanied by rain, so road flooding is inevitable. Since the city's drainage system is connected, flooded edges are always those with the lowest altitudes.

We use a water level to describe the intensity of the rainfall, defined as follows: all edges with an altitude not exceeding the water level are flooded.

Yazid is an OIer from the City of Magic. Having just finished ION2018, he is embarking on his journey back to his warm home.

Yazid's home is exactly at node $1$ in the City of Magic. For the next $Q$ days, each day Yazid will tell you his starting point $v$ and the water level $p$ for that day.

Every day, Yazid has a car at his starting point. Due to some malfunctions, this car cannot pass through flooded edges.

Yazid can get out of 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 out and will not be used again.

• It should be noted that the car is reset the next day, which means:
  • The car is ready at the new starting point.
  • Yazid cannot use a car parked somewhere previously.

Yazid hates walking in the rain, so he wants to minimize the total length of the edges he walks through while achieving his goal of returning home. Please help Yazid with the calculations.

Some test cases in this problem will be forced online; please see "Input" and "Subtasks" for details.

Input

A single test case contains multiple data sets. The first line of the input contains a non-negative integer $T$, representing the number of data sets.

Each data set is described as follows:

• The first line contains $2$ non-negative integers $n, m$, representing the number of nodes and edges, respectively.
• The next $m$ lines each contain $4$ 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 $3$ non-negative integers $Q, K, S$, where:
  • $Q$ is the total number of days,
  • $K \in \{0, 1\}$ is a coefficient used below,
  • $S$ is the maximum possible water level.
• The next $Q$ lines describe the situation for each day. Each line contains $2$ integers $v_0, p_0$ describing a day:
  • The starting node for this day is $v = (v_0 + K \times \text{lastans} - 1) \bmod n + 1$.
  • The water level for this day is $p = (p_0 + K \times \text{lastans}) \bmod (S + 1)$.
  • Here, $\text{lastans}$ represents the answer from the previous day (the minimum total walking distance). Specifically, we define $\text{lastans} = 0$ for the first day.
  • Here, we guarantee $1 \leq v_0 \leq n, 0 \leq p_0 \leq S$.

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

Output

Output the answers for each data set in sequence. For each data set:

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

Examples

Input 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 1

0
50
200
50
150

Note 1

On the first day, there is no rainfall, and Yazid can take the car directly home.

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

For the second day, Yazid starts at node $2$ and can only take the car to node $3$, which does not help him get home. Therefore, Yazid must walk all the way home.

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

For the fourth day, Yazid can take the car to node $2$ and then walk home.

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

Input 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 2

0
2
3
1

Note 2

This data set is forced 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$.

Subtasks

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

• $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 nodes are connected directly or indirectly by edges.

For your convenience, we use simple descriptions in the table. Here is the formal explanation of these terms:

• Graph Structure: For test cases where this is "Tree" or "Chain", it is guaranteed that $m = n - 1$. Additionally, these two types satisfy the following:
  • Tree: The input graph is guaranteed to be a tree (no cycles).
  • Chain: All edges satisfy $u + 1 = v$.
• Altitude: For test cases where this is "One type", it is guaranteed that $a = 1$ for all edges.
• Forced Online: For test cases where this is "Yes", it is guaranteed that $K = 1$; if "No", then $K = 0$.
• For all test cases, if the corresponding item is "Not guaranteed", no assumptions are made about that item.