RPG 世界里的相同地图

题目描述

高桥正在开发一个 RPG。他决定编写一段代码,用于检查两张地图是否相同。

我们有两张网格 $A$ 和 $B$,各有 $H$ 行、$W$ 列。每个格子中写有符号 # 或 .。

在 $A$ 中,从上数第 $i$ 行、从左数第 $j$ 列的格子中写着的符号记为 $A_{i, j}$;在 $B$ 中对应位置的符号记为 $B_{i, j}$。

下面两种操作分别称为「纵向平移」和「横向平移」。

纵向平移:对每个 $j=1, 2, \dots, W$,同时将 $A_{1,j}, A_{2,j}, \dots, A_{H-1, j}, A_{H,j}$ 替换为 $A_{2,j}, A_{3,j}, \dots, A_{H,j}, A_{1,j}$。

横向平移:对每个 $i = 1, 2, \dots, H$,同时将 $A_{i,1}, A_{i,2}, \dots, A_{i,W-1}, A_{i,W}$ 替换为 $A_{i, 2}, A_{i, 3}, \dots, A_{i,W}, A_{i,1}$。

是否存在一对非负整数 $(s, t)$ 满足以下条件?若存在输出 Yes,否则输出 No。

将 $A$ 进行 $s$ 次纵向平移、$t$ 次横向平移后,$A$ 与 $B$ 相等。

这里,当且仅当对所有满足 $1 \leq i \leq H$ 且 $1 \leq j \leq W$ 的整数对 $(i, j)$,都有 $A_{i, j} = B_{i, j}$ 时,称 $A$ 与 $B$ 相等。

输入格式

输入按以下格式从标准输入给出:

$H$ $W$
$A_{1,1}A_{1,2}\dots A_{1,W}$
$A_{2,1}A_{2,2}\dots A_{2,W}$
$\vdots$
$A_{H,1}A_{H,2}\dots A_{H,W}$
$B_{1,1}B_{1,2}\dots B_{1,W}$
$B_{2,1}B_{2,2}\dots B_{2,W}$
$\vdots$
$B_{H,1}B_{H,2}\dots B_{H,W}$

输出格式

如果存在满足条件的整数对 $(s, t)$,输出 Yes;否则输出 No。

样例

4 3
..#
...
.#.
...
#..
...
.#.
...

Yes

选择 $(s, t) = (2, 1)$,得到的 $A$ 与 $B$ 相等。

下面描述选择 $(s, t) = (2, 1)$ 的过程。初始时 $A$ 如下:

..#
...
.#.
...

先进行一次纵向平移,$A$ 变为:

...
.#.
...
..#

再进行一次纵向平移,$A$ 变为:

.#.
...
..#
...

最后进行一次横向平移,$A$ 变为如下,与 $B$ 相等:

#..
...
.#.
...

3 2
##
##
#.
..
#.
#.

No

无论选择怎样的 $(s, t)$,都无法使 $A$ 与 $B$ 相等。

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

Yes

10 30
..........##########..........
..........####....###.....##..
.....##....##......##...#####.
....####...##..#####...##...##
...##..##..##......##..##....#
#.##....##....##...##..##.....
..##....##.##..#####...##...##
..###..###..............##.##.
.#..####..#..............###..
#..........##.................
................#..........##.
######....................####
....###.....##............####
.....##...#####......##....##.
.#####...##...##....####...##.
.....##..##....#...##..##..##.
##...##..##.....#.##....##....
.#####...##...##..##....##.##.
..........##.##...###..###....
...........###...#..####..#...

Yes

数据范围

• $2 \leq H, W \leq 30$
• $A_{i,j}$ 为 # 或 .,$B_{i,j}$ 也同样。
• $H$ 和 $W$ 为整数。