题目描述

高桥君居住的城市呈长方形，被划分为网格状的区块。长方形的每条边都与东西或南北方向平行。每个区块要么是道路，要么是围墙。高桥君只能在道路上沿东西南北方向移动，不能斜向移动。同时，围墙区块无法通过。

请判断高桥君能否在不破坏围墙的情况下，仅通过道路到达鱼店。

输入格式

输入通过标准输入按以下格式给出。

$H$ $W$
$c_{0,0}$ $c_{0,1}$ ... $c_{0,W-1}$
$c_{1,0}$ $c_{1,1}$ ... $c_{1,W-1}$
:
$c_{H-1,0}$ $c_{H-1,1}$ ... $c_{H-1,W-1}$

• 第 $1$ 行包含两个整数 $H$（城市南北方向长度，$1 \leq H \leq 500$）和 $W$（东西方向长度，$1 \leq W \leq 500$），以空格分隔。
• 接下来的 $H$ 行，每行包含 $W$ 个字符 $c_{i,j}$（$0 \leq i \leq H-1,\ 0 \leq j \leq W-1$），表示网格中每个区块的状态。
  • 第 $i$ 行第 $j$ 个字符 $c_{i,j}$ 取值为 s、g、.、# 之一，表示坐标 $(j, i)$ 的区块状态：
    • s ：该区块为高桥君的家。
    • g ：该区块为鱼店。
    • . ：该区块为道路。
    • # ：该区块为围墙。
  • 高桥君可以通过家、鱼店和道路，但不能通过围墙。
  • 不能走出给定城市的范围。
  • s 和 g 各出现一次。

输出格式

如果能够在不破坏任何围墙的情况下，从家到达鱼店，输出 Yes；否则输出 No。输出仅一行。

输入输出样例

4 5
s####
....#
#####
#...g

No

4 4
...s
....
....
.g..

Yes

10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
###.#.#.#.
#.....#...

No

10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
#.#.#.#.#.
#.....#...

Yes

1 10
s..####..g

No