問題文

ゲーム開発班のメンバーが迷路から脱出するゲームを作りました。

攻略する迷路は $H$ 行 $W$ 列のグリッドで表され、各マスは空きマスか壁です。グリッドの上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表します。

また、迷路のいずれかの空きマスにはプレイヤー、敵、ゴール地点があります。

各マスは $H$ 個の文字列 $S_1,S_2,\dotsc,S_H$ で表され、

• $S_i$の $j$文字目が # のとき、$(i,j)$ は壁
• $S_i$の $j$文字目が . のとき、$(i,j)$ は空きマス
• $S_i$の $j$文字目が S のとき、$(i,j)$ はプレイヤーのスタート地点
• $S_i$の $j$文字目が G のとき、$(i,j)$ はゴール地点
• $S_i$の $j$文字目が E のとき、$(i,j)$ は敵のスタート地点

となっています。

このグリッド上でプレイヤーはゲームをします。

このゲームはプレイヤーと敵のターン制で進行し、先攻はプレイヤーです。

プレイヤーは自分のターンのおいて、隣接する空きマスに移動するか、移動しないことができます。

敵は自分のターンにおいて、現在のプレイヤーの位置まで到達するまでに経由しなければならない空きマスの数が少なくなるような、隣接する空きマスに移動します。

なお、そのような空きマスが複数存在する場合、上、右、下、左の優先順位で移動します。

プレイヤーと敵が同じマスに存在するようになった場合、プレイヤーの敗北です。

プレイヤーが敗北せずにゴール地点まで到達できるか判定してください。

なお、簡単のため、以下の条件を満たす $i,j (1 \leq i \leq H - 2,1 \leq j \leq W - 2)$ が存在しない入力のみが与えられます。

• $(i,j),(i + 1,j),(i,j + 1),(i + 1,j + 1)$ がすべて空きマスである

制約

• $2 \leq H,W \leq 800$
• $H,W$ は整数
• $S_i$ は長さ $W$ の #,.,S,G,E のみからなる文字列
• $S_i$ の $j$ 文字目が S となる $(i,j)$ の組はちょうど$1$つ
• $S_i$ の $j$ 文字目が G となる $(i,j)$ の組はちょうど$1$つ
• $S_i$ の $j$ 文字目が E となる $(i,j)$ の組はちょうど$1$つ

入力

入力は以下の形式で標準入力から与えられます。

出力

プレイヤーが敗北せずにゴール地点に到達できるならばYes、そうでないならばNoと出力してください。

サンプル

4 4
#E##
#.#G
#...
#S##

Yes

プレイヤーはゴールまで直行することで攻略可能です。

4 4
#G##
#.#S
#...
#E##

No

どのように動いたとしても、プレイヤーは敵と同じマスに到達してしまうため、攻略不可能です。

4 4
#.E#
G.##
##.S
####

No

敵の行動にかかわらず、攻略不可能な場合もあります。

7 16
#S##############
#.##...........#
#.#..#.####.####
#...##.####....#
#.#..#.#E#####.#
#.##...........#
##############G#

Yes