402889: GYM100935 J Weird Maze

“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 R_x1, y1 ,"row x1 and column y1", to room R_x2, 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 R_x, y, it’s now the year 0. Tareq wants to travel to the room R_a, 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 R_x, 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 R_x1, y1 , to room R_x2, 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 R_a, b at year w? Starting from the initial position R_x, 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.

3
2 2 1 1
1
1 1 2 2 5 1
1
2 2 1
3 6 1 1
5
1 1 2 5 1 -5
2 5 1 2 1 -7
1 1 1 2 1 5
1 1 1 3 1 3
1 2 1 3 1 8
4
1 1 0
1 2 5
1 3 13
1 3 3
2 2 1 1
4 1
1 2 2 1 5
2 2 1 1 2 5
1 1 2 2 3 -5
2 2 1 1 4 -5
1
2 2 17

Case 1:
5
Case 2:
0
1
2
1
Case 3:
No