Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Infinite Maze

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputWe've got a rectangular *n* × *m*-cell maze. Each cell is either passable, or is a wall (impassable). A little boy found the maze and cyclically tiled a plane with it so that the plane became an infinite maze. Now on this plane cell (*x*, *y*) is a wall if and only if cell is a wall.

In this problem is a remainder of dividing number *a* by number *b*.

The little boy stood at some cell on the plane and he wondered whether he can walk infinitely far away from his starting position. From cell (*x*, *y*) he can go to one of the following cells: (*x*, *y* - 1), (*x*, *y* + 1), (*x* - 1, *y*) and (*x* + 1, *y*), provided that the cell he goes to is not a wall.

Input

The first line contains two space-separated integers *n* and *m* (1 ≤ *n*, *m* ≤ 1500) — the height and the width of the maze that the boy used to cyclically tile the plane.

Each of the next *n* lines contains *m* characters — the description of the labyrinth. Each character is either a "#", that marks a wall, a ".", that marks a passable cell, or an "S", that marks the little boy's starting point.

The starting point is a passable cell. It is guaranteed that character "S" occurs exactly once in the input.

Output

Print "Yes" (without the quotes), if the little boy can walk infinitely far from the starting point. Otherwise, print "No" (without the quotes).

Examples

Input

5 4

##.#

##S#

#..#

#.##

#..#

Output

Yes

Input

5 4

##.#

##S#

#..#

..#.

#.##

Output

No

Note

In the first sample the little boy can go up for infinitely long as there is a "clear path" that goes vertically. He just needs to repeat the following steps infinitely: up, up, left, up, up, right, up.

In the second sample the vertical path is blocked. The path to the left doesn't work, too — the next "copy" of the maze traps the boy.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/30/2017 21:55:37 (c4).

Desktop version, switch to mobile version.
User lists

Name |
---|