CF196B.Infinite Maze

We'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.

我们有一个 $ n \times m $ 的矩形迷宫，每个格子要么是可通过的，要么是墙（不可通过）。一个小男孩发现了这个迷宫，并将其在平面上进行循环铺砌，从而得到一个无限大的迷宫。此时，平面上的格子 $ (x, y) $ 是墙，当且仅当原始迷宫中的格子

是墙。

本题中， 表示数 $ a $ 除以数 $ b $ 所得的余数。

小男孩站在平面上的某个格子上，并思考自己是否能从起始位置出发，行走至离起点任意远的位置。从格子 $ (x, y) $ 出发，他可以移动到以下四个格子之一：$ (x, y - 1) $、$ (x, y + 1) $、$ (x - 1, y) $、$ (x + 1, y) $，前提是目标格子不是墙。

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.

第一行包含两个以空格分隔的整数 $n$ 和 $m$（$1 \leq n, m \leq 1500$）——分别表示男孩用于周期性铺满平面的迷宫的高度与宽度。

接下来的 $n$ 行，每行包含 $m$ 个字符，描述该迷宫。每个字符要么是 "#"（表示一堵墙），要么是 "."（表示一个可通过的单元格），要么是 "S"（表示小男孩的起始位置）。

起始位置是一个可通过的单元格。保证输入中恰好出现一次字符 "S"。

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

如果小男孩能够从起点出发无限远地行走，则输出 "Yes"（不带引号）；否则，输出 "No"（不带引号）。

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.

在第一个样例中，小男孩可以无限向上移动，因为存在一条垂直的“畅通路径”。他只需无限重复以下步骤：上、上、左、上、上、右、上。

在第二个样例中，垂直路径被阻挡。向左的路径也不可行——下一个迷宫的“副本”会困住小男孩。