Beto is playing a game called "Impossible Mission" and he is getting very angry. He got completely stuck on the final mission. Here's what's the mission is about: Ethan Hunt must simply walk from a given start field to an end one. Hindering his progress, there are fake floor tiles that he must avoid. However that's not all, there are cameras everywhere!

Camera i has range Ri and can be directed in four cardinal directions. It will scan Ri fields in a given direction, not including field were it's placed itself. Every second camera will rotate 90 degrees clock-wise.

Ethan can move only in the four cardinal directions. He must make exactly one move every second (he can't stand in place). In addition, Ethan Hunt can use a special suit that makes him invisible to the cameras, even if he is in the range of multiples cameras. Unfortunately, as everything in the IMF, the suit is a prototype and tends to fail after a second of use. That's ́why Ethan has C suits that he will be able to use. It's possible Ethan will start on a field screened by a camera. In such a case he must use a suit. If he doesn't have one, the game is already lost. Also for final position, you must use a suit to shield against screening before exiting, if you are spotted by a camera.

Your mission, if you choose to accept it, is to help Beto to succeed in the game by telling him whether if it is possible or not to cross the maze. If it is possible, give Beto a clue and output the minimum steps needed to solve the problem.

Input

The first line contains an integer T, which specifies the number of test cases. Then the descriptions of T test cases follow.

For each case, first line will contain four integers N, M, K, C denoting the height and the width of the matrix, the number of cameras and the number of camouflage suits Ethan has.

Next N lines will follow with M characters each. The ’#’ character denotes a fake floor and Ethan must avoid it. The ’.’ denotes a normal floor. Note than a fake floor will only block Ethan and not a camera field of view.

Next K lines will follow with the description of the cameras. Each line will consist on four integers, denoting respectively the row and the column where the camera is (both 0-based), the range Ri of the camera and it's initial direction Di. 0 means that the camera is pointing to north, 1 east, 2 south and 3 west.

Final two lines will contain two integers each, denoting the starting point and the ending point of Ethan Hunt. For both lines, first integer describes the row and second the column, both 0-based. It is guaranteed that Ethan won't start or be directed to a fake floor.

Output

For each input case, you must print a single line. The string "Scenario #i: " where i denotes the case you are analyzing (starting by 1), followed by the minimum number of steps that Ethan must make in order to reach his destination. If it is impossible, print -1.

Example

2
5 4 3 0
....
.#..
..#.
....
....
0 3 4 2
2 1 4 0
4 0 1 0
0 0
4 3
3 3 2 0
...
...
...
0 2 1 2
2 0 1 3
0 0
2 2

Scenario #1: 7
Scenario #2: -1

Constraints - Subtask 1 (30%)

 1 ≤ T ≤ 30

 1 ≤ N ,M ≤ 100

 1 ≤ K ≤ 100

 0 ≤ C ≤ 0

 1 ≤ Rk ≤ 100

Constraints - Subtask 2 (30%)

 1 ≤ T ≤ 20

 1 ≤ N ,M ≤ 100

 1 ≤ K ≤ 100

 0 ≤ C ≤ 10

 1 ≤ Rk ≤ 100

Constraints - Subtask 3 (40%)

 1 ≤ T ≤ 10

 1 ≤ N ,M ≤ 1000

 1 ≤ K ≤ 1000

 0 ≤ C ≤ 10

 1 ≤ Rk ≤ 1000