You are given an undirected connected graph with vertices labeled from to , and edges, where the -th edge has length and altitude .

You are given queries. In each query, you are given a starting vertex , a water level . A water level indicates that there is water on the edges that have . You can drive a car starting from only through the edges that have **no water**, and then get out of the car at any vertex and walk to vertex . You want to find the minimum sum of lengths of edges that you need to **walk** through in a path.

In some tests, the queries are forced online. See more details in the Input Specification/Constraints.

#### Input Specification

The first line contains an integer , the number of test cases.

For each test case,

- The first line contains two non-negative numbers , the number of vertices, and , the number of edges.
- Each of the next lines contains four integers , indicating that the -th edge is between vertices and , and has length and altitude .
- The next line contains three integers, . is a constant used in calculating the input each time, is the highest possible in all queries.
- Each of the next lines contains two integers and . Let denote the answer in the last query ( if this is the first query). Then in this query, you are starting from vertex and water level . It is guaranteed that , .

#### Output Specification

For each query, output the answer on its own line.

#### Constraints

For all test files, . For all test cases in a file:

- .
- For all edges, , , .
- The graph is connected.

The following terminology is used in the constraint table:

- Graph Property:
- Bamboo: , and for each edge we have .
- Tree:

- Altitude:
- One kind: For all edges, .

- Forced Online:
- Yes:
- No:

"no guarantee" means that there is no guarantee on the property of test data.

No. | Graph Property | Altitute | Forced Online | |||
---|---|---|---|---|---|---|

no guarantee | one kind | No | ||||

Bamboo | no guarantee | |||||

Tree | ||||||

Yes | ||||||

no guarantee | No | |||||

Yes | ||||||

#### 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
```

#### Explanation for Sample Output 1

Day has no rain. so you can just travel directly.

Days , , have the same situation: the edges between and have water.

On day , starting from , you can only go to , which doesn't help returning, so you have to walk.

On day , the only edge out of has water, so you again have to walk.

On day , you can first take the car to , and then walk home.

On day , all edges have water, so you have to walk.

#### 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
```

#### Explanation for Sample Output 2

This test case is forced online.

On day the answer is , so day has , .

On day , the answer is , so day has , .

On day , the answer is , so day has , .

## Comments