配点 : $300$ 点

問題文

# と . からなる $H$ 行 $W$ 列の図形 $S,T$ が与えられます。 図形 $S$ は $H$ 個の文字列として与えられ、 $S_i$ の $j$ 文字目は $S$ の $i$ 行 $j$ 列にある要素を表します。 $T$ についても同様です。

$S$ の列を並べ替えて $T$ と等しくできるか判定してください。

但し、図形 $X$ の列を並べ替えるとは、以下の操作を言います。

• $(1,2,\dots,W)$ の順列 $P=(P_1,P_2,\dots,P_W)$ をひとつ選択する。
• その後、全ての $1 \le i \le H$ を満たす整数 $i$ について、以下の操作を同時に行う。- $1 \le j \le W$ を満たす全ての整数 $j$ について同時に、 $X$ の $i$ 行 $j$ 列にある要素を $i$ 行 $P_j$ 列にある要素に置き換える。
• $1 \le j \le W$ を満たす全ての整数 $j$ について同時に、 $X$ の $i$ 行 $j$ 列にある要素を $i$ 行 $P_j$ 列にある要素に置き換える。

制約

• $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 と出力せよ。

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

Yes

例えば $S$ の $3,4,2,1$ 列目をこの順に左から並べ替えた場合、 $S$ を $T$ と等しくできます。

3 3
#.#
.#.
#.#
##.
##.
.#.

No

この入力では、 $S$ を $T$ と等しくすることができません。

2 1
#
.
#
.

Yes

$S=T$ である場合もあります。

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

Yes