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

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

As a city with a monsoon climate, the Magic City is often accompanied by rain, so road flooding is inevitable. Since the city's drainage system is connected, the edges with flooding are always those with the lowest altitudes. We use a water level line to describe the degree of rainfall, which means: all edges with an altitude not exceeding the water level line are flooded.

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

Yazid's home is exactly at node $1$ of the Magic City. For the next $Q$ days, every day Yazid will tell you his starting point $v$ and the water level line $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 off 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 should be specifically noted that the car will be reset the next day, which means:
  • The car will be ready at the new starting point.
  • Yazid cannot use a car that was left somewhere previously.

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

Some test cases for this problem will be forced online; for details, please see the Input and Subtasks sections.

Input

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

The following describes each data set in order. For each data set:

• The first line contains two non-negative integers $n, 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 \le u, v \le n$.
• The next line contains three non-negative integers $Q, K, S$, where $Q$ represents the total number of days, $K \in \{0, 1\}$ is a coefficient used below, and $S$ represents the maximum possible water level.
• The next $Q$ lines describe the situation for each day. Each line contains two integers $v_0, p_0$ describing a day:
  • The starting node for this day is $v = (v_0 + K \times \text{lastans} - 1) \pmod n + 1$.
  • The water level for this day is $p = (p_0 + K \times \text{lastans}) \pmod {(S + 1)}$.
  • Where $\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 \le v_0 \le n$ and $0 \le p_0 \le S$.

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

Output

Output the answers for each data set in order. 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

On the first day, there is no precipitation, 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 from node $2$ and can only take the car to node $3$, which does not help him get home. Therefore, Yazid must walk home.

For the third day, the only edge from node $4$ is flooded, so the car becomes useless. Yazid must walk 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 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

This data set is forced online.

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

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

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

Subtasks

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

• $n \le 2 \times 10^5$, $m \le 4 \times 10^5$, $Q \le 4 \times 10^5$, $K \in \{0, 1\}$, $1 \le S \le 10^9$.
• For all edges: $l \le 10^4$, $a \le 10^9$.
• Any two nodes are connected directly or indirectly by edges.

To facilitate your understanding, we have used some simple descriptions in the table. Here, we provide a formal explanation of these contents:

• Graph Topology: For test cases where this item in the table is "Tree" or "Chain", it is guaranteed that $m = n - 1$. In addition, these two types of test cases satisfy the following limits:
  • Tree: It is guaranteed that the input graph is a tree, i.e., edges do not form cycles.
  • Chain: It is guaranteed that all edges satisfy $u + 1 = v$.
• Altitude: For test cases where this item in the table is "Uniform", it is guaranteed that $a = 1$ for all edges.
• Forced Online: For test cases where this item in the table is "Yes", it is guaranteed that $K = 1$; if it is "No", then $K = 0$.
• For all test cases, if the corresponding item above is "Not guaranteed", no guarantee is made for that content.

Hints

• Example 3 satisfies Altitude as "Uniform" and is not forced online.
• Example 4 satisfies Graph Topology as "Chain" and is forced online.
• Example 5 satisfies not being forced online.