/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
# と . からなる H 行 W 列の図形 S,T が与えられます。
図形 S は H 個の文字列 S _ 1,S _ 2,\ldots,S _ H として与えられ、 S _ i の j 文字目は S の i 行 j 列にある要素を表します。 T についても同様です。
S の列をシフトして T と等しくできるか判定してください。
ただし、図形 X の列をシフトするとは、以下の操作を言います。
- 1 以上 W 以下の整数 s をひとつ選択する。
- その後、全ての 1 \leq i \leq H を満たす整数 i について、以下の操作を同時に行う。
- 1 \leq j \leq W を満たす全ての整数 j について同時に、 X の i 行 j 列にある要素を i 行 j+s 列にある要素に置き換える。
ただし、ここでは W \gt x となる x に対して x 列と書いたとき、x-y が W の倍数となるような唯一の整数 y\ (1\leq y\leq W) について y 列のことを指すとします。
制約
- H,W は整数
- 1 \le H,W
- 1 \le H \times W \le 4 \times 10^5
- S_i,T_i は
#と.からなる長さ W の文字列
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 \vdots S_H T_1 T_2 \vdots T_H
出力
S を T と等しくできるなら Yes 、 そうでないなら No と出力せよ。
入力例 1
3 4 ##.# ##.. .#.. .### ..## ...#
出力例 1
Yes
s=2 とすると、S を T と等しくできます。
入力例 2
3 4 ##.. #..# ..## ..## #..# ##..
出力例 2
No
列をシフトすることはできますが、図形を反転させることはできません。
入力例 3
2 1 # . # .
出力例 3
Yes
S=T である場合もあります。
入力例 4
8 7 .#..... ..#.... ....#.. #.....# .#..... ..#.... ....#.. #.....# .....#. ......# .#..... ...##.. .....#. ......# .#..... ...##..
出力例 4
Yes
Problem Statement
You are given figures S and T with H rows and W columns consisting of # and ..
The figure S is given as H strings S _ 1,S _ 2,\ldots,S _ H; the j-th character of S _ i represents the element at the i-th row and j-th column of S. The figure T is given similarly.
Determine whether it is possible to shift the columns of S so that S will equal T.
Here, shifting the columns of S is the following operation.
- Choose an integer s between 1 and W, inclusive.
- Then, for every integer i such that 1 \leq i \leq H, simultaneously perform the following:
- for every integer j such that 1 \leq j \leq W, simultaneously replace the element at the i-th row and j-th column with that of the i-th row and (j+s)-th column of X.
Here, for x such that W \gt x, the x-th column means the y-th column where y\ (1\leq y\leq W) is the only integer such that x-y is a multiple of W.
Constraints
- H and W are integers.
- 1 \le H,W
- 1 \le H \times W \le 4 \times 10^5
- S_i and T_i are strings of length W consisting of
#and..
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H T_1 T_2 \vdots T_H
Output
If it is possible to make S equal T, print Yes; otherwise, print No.
Sample Input 1
3 4 ##.# ##.. .#.. .### ..## ...#
Sample Output 1
Yes
Choosing s=2 will make S equal T.
Sample Input 2
3 4 ##.. #..# ..## ..## #..# ##..
Sample Output 2
No
You can only shift the columns and not turn over the figure.
Sample Input 3
2 1 # . # .
Sample Output 3
Yes
It may be the case that S=T.
Sample Input 4
8 7 .#..... ..#.... ....#.. #.....# .#..... ..#.... ....#.. #.....# .....#. ......# .#..... ...##.. .....#. ......# .#..... ...##..
Sample Output 4
Yes