atcoder#ABC279C. [ABC279C] RANDOM

[ABC279C] RANDOM

Score : 300300 points

Problem Statement

You are given patterns SS and TT consisting of # and ., each with HH rows and WW columns. The pattern SS is given as HH strings, and the jj-th character of SiS_i represents the element at the ii-th row and jj-th column. The same goes for TT.

Determine whether SS can be made equal to TT by rearranging the columns of SS.

Here, rearranging the columns of a pattern XX is done as follows.

  • Choose a permutation P=(P1,P2,,PW)P=(P_1,P_2,\dots,P_W) of (1,2,,W)(1,2,\dots,W).
  • Then, for every integer ii such that 1iH1 \le i \le H, simultaneously do the following. - For every integer jj such that 1jW1 \le j \le W, simultaneously replace the element at the ii-th row and jj-th column of XX with the element at the ii-th row and PjP_j-th column.
  • For every integer jj such that 1jW1 \le j \le W, simultaneously replace the element at the ii-th row and jj-th column of XX with the element at the ii-th row and PjP_j-th column.

Constraints

  • HH and WW are integers.
  • 1H,W1 \le H,W
  • 1H×W4×1051 \le H \times W \le 4 \times 10^5
  • SiS_i and TiT_i are strings of length WW consisting of # and ..

Input

The input is given from Standard Input in the following format:

HH WW

S1S_1

S2S_2

\vdots

SHS_H

T1T_1

T2T_2

\vdots

THT_H

Output

If SS can be made equal to TT, print Yes; otherwise, print No.

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

If you, for instance, arrange the 33-rd, 44-th, 22-nd, and 11-st columns of SS in this order from left to right, SS will be equal to TT.

3 3
#.#
.#.
#.#
##.
##.
.#.
No

In this input, SS cannot be made equal to TT.

2 1
#
.
#
.
Yes

It is possible that S=TS=T.

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