/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
問題文
# と . からなる H 行 W 列の図形 S,T が与えられます。
図形 S は H 個の文字列 S _ 1,S _ 2,\ldots,S _ H として与えられ、 S _ i の j 文字目は S の i 行 j 列にある要素を表します。 T についても同様です。
S を行ごとに並べ替えて T と等しくできるか判定してください。
ただし、図形 X を行ごとに並べ替えるとは、以下の操作を言います。
- i=1,2,\ldots,H のそれぞれについて、独立に次の操作を行う。
- (1,2,\ldots,W) の順列 P=(P _ 1,P _ 2,\ldots,P _ W) をひとつ選択する。
- 1 \leq j \leq W を満たす全ての整数 j について同時に、 X の i 行 j 列にある要素を i 行 P_j 列にある要素に置き換える。
異なる i に対して異なる順列 P を選んでもよいことに注意してください。
制約
- H,W は整数
- 1 \leq H,W
- 1 \leq H \times W \leq 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
例えば i=1,2,3 について P としてそれぞれ (4,2,1,3),(1,3,4,2),(4,1,3,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 one can rearrange each row of S to make S equal T.
Here, rearranging each row of a figure X is the following operation.
- For each i=1,2,\ldots,H, perform the following procedure independently.
- Choose a permutation P=(P _ 1,P _ 2,\ldots,P _ W) of (1,2,\ldots,W).
- For all integers j such that 1 \leq j \leq W, simultaneously replace the element at the i-th row and j-th column of X with the one at the i-th row and P_j-th column.
Note that you may choose different permutations P for different i.
Constraints
- H and W are integers.
- 1 \leq H,W
- 1 \leq H \times W \leq 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
Print Yes if one can make S equal T; print No otherwise.
Sample Input 1
3 4 ##.# ##.. .#.. ###. #..# ...#
Sample Output 1
Yes
For example, if you choose (4,2,1,3),(1,3,4,2),(4,1,3,2) for i=1,2,3, respectively, you can make S equal T.
Sample Input 2
3 4 #... #..# .### ..## #..# ##..
Sample Output 2
No
Sample Input 3
2 1 # . # .
Sample Output 3
Yes
S=T may hold.
Sample Input 4
8 7 ..#.#.# ..#.... #.#.... ..#.#.# ..#..#. ..#...# ..#.... #.#.... ##.#... ...#... #..#... ..#..## ...#.#. ....#.# ......# #....#.
Sample Output 4
Yes