Maze

Time Limit: 1 Second    Memory Limit: 32768 KB

ACM, an treasure-explorer ,is exploring again. This time he is in a special maze ,in which there are some doors(at most 5 doors ,represented by 'A','B','C','D','E' respectively).In order to find the treasure, ACM may need to open doors.However, to open a door you need to find all the door's keys (at least one) in the maze first. For example, there are 3 keys of Door A,to open the door you should first find all the 3 keys first(that's three 'a' which denotes the key of 'A' in the maze). Now make a program to tell ACM whether he can find the treasure. Notice that ACM can only go up,down ,left ,right in the maze.

Input

The input consists of multiple test cases. The first line of each test case contains three integers M, N, (1 < N, M < 20), which denote the sizes of the maze . The next M lines give the maze layout, with each line containing N characters. A character is one of the following: 'X': a block of wall, which the explorer cannot enter; 'S': the start point of ACM; 'A,B,C,D,E': the Doors; 'a,b,c,d,e' : the Keys of the doors, respectively ; '.': an empty block; 'G': the position of treasure The input is terminated with two 0's. This test case is not to be processed.

Output

For each test case, print in one line "YES" if ACM can find the treasure, or "NO" otherwise.

Sample Input

4 4
S.X.
..X.
..XG
....
3 4
S.Xa
.aXB
..AG
0 0

Sample Output

YES
NO

Submit

Source: ZOJ Monthly, January 2005