题目描述

高先生住的小区是长方形的，被划分成一个个格子。高先生想从家里去鱼店，高先生每次可以走到他前后左右四个格子中的其中一个，但不能斜着走，也不能走出小区。

现在给出地图：

• s：代表高先生的家
• g：代表鱼店
• .：代表道路
• #：代表墙壁

高先生不能穿过墙壁。如果高先生能到达鱼店，输出 Yes，否则输出 No。

输入格式

第一行：两个整数 $n, m$，代表小区的长和宽。 接下来 $n$ 行：每行 $m$ 个字符，描述小区中的每个格子。

数据范围：$1 \le n \le 300$，$1 \le m \le 300$。

输出格式

一行，Yes 或者 No（不带引号）。

样例 #1

样例输入 #1

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

样例输出 #1

No

样例解释 #1

我们将样例地图坐标化（行号从 1 到 10，列号从 1 到 10）：

• 起点 s 位于 $(1,1)$；
• 终点 g 位于 $(7,1)$；
• 第 2 行除了最后一列外全是墙壁 #，形成了一道横向屏障；
• 从 $(1,1)$ 出发，无法穿过第 2 行的墙壁到达下方的 $(7,1)$，因此高先生不能到达鱼店，输出 No。

提示

$1 \le n \le 300$，$1 \le m \le 300$。