“Weird Mazes” are defined as the following:
* The maze has rectangular shape, it has N rows and M columns of rooms.
* The rows are numbered from 1 to N top to down, the columns are numbered from 1 to M left to right.
* Each room is connected to at most 6 other rooms, through magical doors, these room are not necessarily the usual top, down, left, or right room.
* To move from room Rx1, y1 ,_"row x1 and column y1"_, to room Rx2, y2, it costs an amount of money C ( 0 < C ≤ 1000 ). In addition, when you move from one room to another you spend T years, where ( - 100 ≤ T ≤ + 100 ), that means: if T is positive, then you are travelling to the future. If T is negative, then you are travelling to the past!
A friend of yours, Tareq, is at room Rx, y, it’s now the year 0. Tareq wants to travel to the room Ra, b, and arrive there exactly in year w, another big problem is: during the trip, the absolute value of time can never exceed 100, In other words: Tareq should always stay in the [-100, +100] time range, because if he didn't, he will be lost in the maze for ever !!
Can you help Tareq to know the minimum cost of money for him trip?
The first line will be the number of test cases Tc. Each test case starts with four integers in a single line: 0 < N ≤ 100, the number of rows in the maze, 0 < M ≤ 100, the number of columns, 0 < x ≤ N , 0 < y ≤ M , the initial position of Tareq meaning that he is in room Rx, y, (Remember he starts at year 0). The second line contains an integer p, the number of connections between rooms in the maze. Then p lines follow, each describe a connection and contains six integers: 0 < x1 ≤ N , 0 < y1 ≤ M , 0 < x2 ≤ N , 0 < y2 ≤ M , 0 < C ≤ 1000 , - 100 ≤ T ≤ + 100 , Which means that there is a one way connection from room Rx1, y1 , to room Rx2, y2 , with cost C of money and T of time. Follows a line containing one integer q, the numbers of queries, each query consists of three integers: 0 < a ≤ N , 0 < b ≤ M , - 100 ≤ w ≤ 100 , which means: what is the minimum cost of money that Tareq has to pay in order to reach room Ra, b at year w? Starting from the initial position Rx, y.
For each test case, you should print "Case c:" without quotes where c is the number of the test case starting from 1, then for each query you should print one integer on a separated line, the solution to the query. If it is impossible to achieve, just print the word "No" without quotes, see the sample output for more details.
## Input
The first line will be the number of test cases Tc. Each test case starts with four integers in a single line: 0 < N ≤ 100, the number of rows in the maze, 0 < M ≤ 100, the number of columns, 0 < x ≤ N , 0 < y ≤ M , the initial position of Tareq meaning that he is in room Rx, y, (Remember he starts at year 0). The second line contains an integer p, the number of connections between rooms in the maze. Then p lines follow, each describe a connection and contains six integers: 0 < x1 ≤ N , 0 < y1 ≤ M , 0 < x2 ≤ N , 0 < y2 ≤ M , 0 < C ≤ 1000 , - 100 ≤ T ≤ + 100 , Which means that there is a one way connection from room Rx1, y1 , to room Rx2, y2 , with cost C of money and T of time. Follows a line containing one integer q, the numbers of queries, each query consists of three integers: 0 < a ≤ N , 0 < b ≤ M , - 100 ≤ w ≤ 100 , which means: what is the minimum cost of money that Tareq has to pay in order to reach room Ra, b at year w? Starting from the initial position Rx, y.
## Output
For each test case, you should print "Case c:" without quotes where c is the number of the test case starting from 1, then for each query you should print one integer on a separated line, the solution to the query. If it is impossible to achieve, just print the word "No" without quotes, see the sample output for more details.
[samples]
**Definitions**
Let $ N, M \in \mathbb{Z}^+ $ denote the number of rows and columns in the maze.
Let $ G = (V, E) $ be a directed graph where:
- $ V = \{ (i, j, t) \mid 1 \leq i \leq N,\ 1 \leq j \leq M,\ -100 \leq t \leq 100 \} $ is the set of states (room position and time).
- Each edge $ e \in E $ corresponds to a connection: from $ (x_1, y_1, t_1) $ to $ (x_2, y_2, t_2) $ with cost $ C $ and time shift $ T $, such that $ t_2 = t_1 + T $, and $ (x_1, y_1) \to (x_2, y_2) $ is given as input.
Let $ (x_s, y_s) \in \{1,\dots,N\} \times \{1,\dots,M\} $ be the starting room, with initial time $ t_s = 0 $.
Let $ (x_q, y_q, w_q) $ be a query: target room and target time.
**Constraints**
1. $ 1 \leq N, M \leq 100 $
2. $ -100 \leq t \leq 100 $ for all time states (time bounded)
3. Each edge has $ 0 < C \leq 1000 $, $ -100 \leq T \leq 100 $
4. For any path, time must remain in $ [-100, 100] $
**Objective**
For each query $ (x_q, y_q, w_q) $, compute:
$$
\min \left\{ \sum_{e \in P} C_e \ \middle|\ P \text{ is a path from } (x_s, y_s, 0) \text{ to } (x_q, y_q, w_q) \right\}
$$
If no such path exists, output "No".