Description

The illusion maze can be regarded as infinite, but it is formed by repeating several $N \times M$ matrices. In the matrix, some cells are roads, denoted by \verb!.!, and some cells are walls, denoted by \verb!#!. The position of LHX and WD is denoted by \verb!S!. That is, for a point $(x,y)$ in the maze, if $(x \bmod n,y \bmod m)$ is \verb!.! or \verb!S!, then this location is a road; if $(x \bmod n,y \bmod m)$ is \verb!#!, then this location is a wall. LHX and WD can move in the four directions up, down, left, and right, and of course they cannot move into walls. Here, $n$ and $m$ refer to $N$ and $M$ respectively.

Please tell LHX and WD whether they can escape from the illusion maze (if they can reach positions at unbounded distance from the starting point, we consider that they can escape). Otherwise, LHX will have to activate the castle’s self-destruction program... but he really does not want to do that unless absolutely necessary.

Input Format

The input contains multiple test cases.

For each test case, the first line contains two integers $N, M$.

Then follows an $N \times M$ character matrix, representing the cells from $(0,0)$ to $(n-1,m-1)$.

Output Format

For each test case, output a string, "Yes" or "No".

5 4
##.#
##S#
#..#
#.##
#..#
5 4
##.#
##S#
#..#
..#.
#.##

Yes
No

Hint

• For 30% of the testdata, $1 \le N, M \le 20$.
• For 50% of the testdata, $1 \le N, M \le 100$.
• For 100% of the testdata, $1 \le N, M \le 1500$, with no more than $10$ test cases per test point.

Translated by ChatGPT 5