列重排

题目描述

给你由 # 和 . 组成的图案 $S$ 和 $T$,它们各有 $H$ 行 $W$ 列。

图案 $S$ 由 $H$ 个字符串给出,$S_i$ 的第 $j$ 个字符表示第 $i$ 行第 $j$ 列的元素。$T$ 同理。

请判断能否通过重排 $S$ 的列,使 $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$ 列的元素。

输入格式

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

$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

数据范围

• $H$、$W$ 均为整数。
• $1 \le H,W$
• $1 \le H \times W \le 4 \times 10^5$
• $S_i$、$T_i$ 是由 # 和 . 组成的长度为 $W$ 的字符串。