There is a graph ~G~ with ~n~ vertices and ~m~ undirected edges. Graph ~G~ is a connected graph, and the vertices are numbered ~1,\ldots,n~. Each edge has a length ~l~ and a weight ~w~.

There are ~Q~ queries. Each query consists of an origin ~v~ and a threshold ~t~. You need to travel from vertex ~v~ back to vertex ~1~. There are two ways of traveling:

• Travel by car: there is a car at origin ~v~, but you can only travel by car along an edge ~e~ if the weight of edge ~e~ is strictly greater than the threshold ~t~.
• Walk: You can get off the car at any time and walk towards vertex 1, but the car will be left at the vertex you get off, and the car cannot be used again for the journey.

For each query, output the minimum total length of edges that you need to walk to get back home. Notice that the queries are independent, which means you cannot pick up the car left at an earlier query and use the car to continue traveling.

For some test cases, you must implement an online algorithm. This is enforced by the parameter ~A~: when ~A = 1~, you can only decode the actual query with the knowledge of the result to the last query. When ~A = 0~, you will get the actual query.

Input Specification

The first line of the input consists of a non-negative integer ~T~ denoting the number of test cases. For each test case:

The first line consists of two non-negative integers ~n,m~ denoting the number of vertices and the number of edges of graph ~G~.

In the following ~m~ lines, each line consists of four positive integers ~u,v,l,w~ denoting that there is an undirected edge between ~u~ and ~v~. The edge has length ~l~ and weight ~w~. It is guaranteed that ~1 \leq u,v \leq n~.

In the following line, there are three non-negative integers ~Q,A,T_{max}~ denoting the number of queries, the coefficient ~A~, and the maximum possible threshold ~T_{max}~.

In the following ~Q~ lines, each line consists of two integers ~v_0,t_0~ specifying a query:

• The actual ~v~ is ~v = \left( (v_0 + A \times \texttt{lastans} - 1) \bmod n \right) + 1~.
• The actual threshold ~t~ is ~t = (t_0 + A \times \texttt{lastans}) \bmod (T_{max} + 1)~.

Here, ~\texttt{lastans}~ represents the answer to the last query, and for the first query, since there are no queries before it, we initialize to ~\texttt{lastans} = 0~. It is guaranteed that ~1 \leq v_0 \leq n~ and ~0 \leq t_0 \leq T_{max}~.

Output Specification

For each query, output a line with an integer denoting the minimum length you have to walk.

Sample 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

Sample Output 1

0
50
200
50
150

Sample 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

Sample Output 2

0
2
3
1

Constraints

For all test cases, ~T \leq 3, n \leq 2 \times 10^5, m \leq 4 \times 10^5, Q \leq 4 \times 10^5, A \in \{0,1\}, 1 \leq T_{max} \leq 10^9~.

For all edges, ~1 \leq l \leq 10^4, 1 \leq w \leq 10^9~.

The graph is connected.

UPDATE: there are no parallel edges or self loops.

Scoring

The subtasks are given below:

• Subtask 1 (1 point): ~n \leq 1, m = 0, Q = 0, A = 0~.
• Subtask 2 (20 points): ~n \leq 1500, m \leq 4000, Q \leq 2000, A = 0~, ~w = 1~ for all edges. Depends on Subtask 1.
• Subtask 3 (9 points): ~Q \leq 10^5, A = 0~, and ~w = 1~ for all edges. Depends on Subtask 1,2.
• Subtask 4 (15 points): ~n \leq 1500, m = n-1, Q \leq 2000~, ~A = 0~. For all edges, ~u + 1 = v~, so the graph forms a chain.
• Subtask 5 (5 points): ~Q \leq 10^5~, ~A = 0~, and the graph is a tree. Depends on Subtask 4.
• Subtask 6 (5 points): ~Q \leq 10^5~, ~A = 1~, and the graph is a tree.
• Subtask 7 (15 points): ~Q \leq 10^5, A = 0~. Depends on Subtask 1,2,3,4,5.
• Subtask 8 (10 points): ~n \leq 1500, m \leq 4000, Q \leq 2000, A = 1~.
• Subtask 9 (10 points): ~Q \leq 10^5, A = 1~. Depends on Subtask 6.
• Subtask 10 (10 points): ~A = 1~. Depends on Subtask 6,9.

Here is a summary of what you can expect:

• Subtasks with ~A = 0~: Subtask 1,2,3,4,5,7 satisfy ~A = 0~, which means we don't require you to implement an online algorithm for these subtasks.
• Subtasks with ~w = 1~ for all edges: Subtask 1,2,3 satisfy ~w = 1~ for all edges.
• Subtasks where the graph is a chain: Subtask 4.
• Subtasks where the graph is a tree: Subtask 5,6.
• Subtasks where ~n \leq 1500~ and ~Q \leq 2000~: Subtask 1,2,4,8.