1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;


char maze[100][100];
bool vis[100][100];
int n,m;
int sx,sy;
int key_num[200]; //钥匙的数量
int key_get[200]; //得到钥匙的数量
bool is_get_key = 0;
int fx[4][2] = {1,0,0,1,-1,0,0,-1};

struct pos{
    int x,y;
};

bool is_key(char c){
    return (c >='a' && c<='e');
}
bool is_door(char c){
    return (c >='A' && c<='E');
}

void init(){
    memset(key_num,0,sizeof(key_num));
    memset(key_get,0,sizeof(key_get));
    int i,j;
    for (i=1;i<=n;i++){
        scanf("%s",maze[i]+1);
    }
    for (i=1;i<=n;i++){
       for (j=1;j<=m;j++){
           char &at = maze[i][j];
           if( is_key(at))
               key_num[at]++;
           else if( at == 'S')
               sx = i,sy =j;
       }
    }
}

bool in_map(int x,int y){
    return (x>=1 && x<=n && y >=1 && y <=m);
}

bool bfs(){
    memset(vis,0,sizeof(vis));
    vis[sx][sy] = 1;
    queue<pos> q;
    q.push({sx,sy});

    while( !q.empty()){
        pos h = q.front(); q.pop();
        int i;
        for (i=0;i<4;i++){
            int nx = h.x+fx[i][0];
            int ny = h.y+fx[i][1];
            if( in_map(nx,ny) && !vis[nx][ny] && maze[nx][ny] != 'X' &&!is_door(maze[nx][ny])){
                char &at = maze[nx][ny];
                if( at == 'G')
                    return 1;
                if( is_key(at)){
                    is_get_key = 1;
                    key_get[at]++;
                    at = '.';
                }
                vis[nx][ny] = 1;
                q.push({nx,ny});
            }
        }
    }
    return 0;
}

void clear_door(char door){
    int i,j;
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++){
            char &at = maze[i][j];
            if( at == door){
                at = '.';
            }
        }
    }
}

void print_maze(){
    int i,j;
    for (i=1;i<=n;i++){
        printf("%s\n",maze[i]+1);
    }
    printf("============\n");
}

bool Find_way(){
    while(1){
        is_get_key = 0;
        bool ret = bfs();
        if( ret) return 1;
        if( !is_get_key)
            return 0;

        /* deal door  */
        int i;
        for(i='a' ;i<= 'e';i++){
            if( key_num[i] != 0 && (key_num[i] == key_get[i])){
                clear_door(i+'A'-'a');
                key_num[i] = 0;
            }
        }

    }
    return 0;
}


int main(){
    while(1){
        scanf("%d%d",&n,&m);
        if( n == 0 || m == 0) return 0;
        init();
        if( Find_way())
            printf("YES\n");
        else 
            printf("NO\n");
    }
    return 0;
}