J. Weird Maze
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

“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?

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.

Examples
Input
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
Output
Case 1:
5
Case 2:
0
1
2
1
Case 3:
No