C :: A Mazing Problem

Time Limit: 1 Second    Memory Limit: 32768 KB

In a maze of size M by N, there is a savage hound named "Fatdog". Fatdog keeps moving around, and will have a good bite at his victim as soon as anyone moves into his sightline. You are supposed to compute the minimum time taken to cross this maze alive, and Fatdog must be for sure avoided.

In every time unit, you may move one block to one of the upper, lower, left and right neighboring blocks, or you may stay where you are. Of course you must not move into the wall, neither must you walk right into Fatdog, and you must not fall into Fatdog's sightline as well. The entrance given is guaranteed to avoid Fatdog's sight.

At the mean time, Fatdog is not as smart as you are -- in every time unit, he either moves forward by one block, or stays and turns 90 degrees to the left or to the right.

Assume that in every time unit you and Fatdog are taking actions simultaneously.

Input

There are several test cases. For each test case:

The first line of input contains 2 integers M and N (0 < M,N <= 50) which indicating the size of a maze, provided that the origin is at the upper-left corner.

The second line contains 7 numbers: x1,y1,x2,y2,x3,y3,D where x1 and y1 are the coordinates of your starting position, x2 and y2 are your exit coordinates, x3 and y3 are the coordinates of the initial position of Fatdog (assuming that he is facing North at every beginning)

The next line contains D(0 < D <= 50) characters, representing Fatdog's actions. When he finishes these D actions, he will be back to his starting position and facing North, and then he will repeat these actions again and again forever (poor Fatdog...). These characters are:

'G' means moving one block forward

'L' means turning 90 degrees to the left

'R' means turning 90 degrees to the right

Then there will be M lines followed, with N characters in each line, describing the maze:

'.' represents an empty block, meaning there is a path.

'*' represents a block of wall.

The input is finished by a pair of 0's as M and N.

Output

For each test case, the first line of output must be in the form "Case d:" where d is the case number (start counting from 1). The second line must be either "Minimal time is: d" where d is the minimum crossing time, or "No way out" meaning that it is impossible to cross the maze alive.

Two test cases must be separated by a blank line.

Sample Input

5 3
3 1 3 3 4 2 8
GGRRGGRR
***
*.*
...
*.*
***
5 3
3 1 3 3 2 2 2
LR
***
*.*
...
*.*
***
3 3
2 1 2 3 2 2 4
RRRR
***
...
***
0 0

Sample Output

Case 1:
Minimal time is: 3

Case 2:
Minimal time is: 2

Case 3:
No way out

Submit

Source: Zhejiang University Local Contest 2002