配点 : $300$ 点

問題文

$2$ 次元グリッド上に $2$ つの図形 $S$ と $T$ があります。グリッドは正方形のマスからなります。

$S$ は $N$ 行 $N$ 列のグリッド内にあり、$S_{i,j}$ が # であるようなマス全体からなります。 $T$ も $N$ 行 $N$ 列のグリッド内にあり、$T_{i,j}$ が # であるようなマス全体からなります。

$S$ と $T$ を $90$ 度回転及び平行移動の繰り返しによって一致させることができるか判定してください。

制約

• $1 \leq N \leq 200$
• $S,T$ は # と . のみからなる
• $S,T$ は $1$ つ以上 # を含む

入力

入力は以下の形式で標準入力から与えられる。

$N$

$S_{1,1}S_{1,2}\ldots S_{1,N}$

$\vdots$

$S_{N,1}S_{N,2}\ldots S_{N,N}$

$T_{1,1}T_{1,2}\ldots T_{1,N}$

$\vdots$

$T_{N,1}T_{N,2}\ldots T_{N,N}$

出力

$S$ と $T$ を$90$ 度回転及び平行移動の繰り返しによって一致させることができるとき Yes を、そうでないとき No を出力せよ。

5
.....
..#..
.###.
.....
.....
.....
.....
....#
...##
....#

Yes

$S$ を左回りに $90$ 度回転させ、平行移動することで $T$ に一致させることができます。

5
#####
##..#
#..##
#####
.....
#####
#..##
##..#
#####
.....

No

$90$ 度回転と平行移動の繰り返しによって一致させることはできません。

4
#...
..#.
..#.
....
#...
#...
..#.
....

Yes

$S$ 及び $T$ は連結とは限りません。

4
#...
.##.
..#.
....
##..
#...
..#.
....

No

回転や移動の操作は連結成分ごとにできるわけではなく、$S,T$ 全体に対して行うことに注意してください。