AT_pakencamp_2025_day1_h Typical Piece Problem

$ N $ 行 $ M $ 列の $ 2 $ つのグリッド $ A,B $ が与えられます。グリッドの各マスは白か黒で塗られており、 `#` はそのマスが黒で、 `.` は白で塗られていることを表します。 ここで、グリッドの隣接頂点を上下左右の $ 4 $ マスとしたときの、黒く塗られたマスが形成する連結成分の形（位置は問わない）の多重集合を、各グリッドについて考えます。 また、ある連結成分に対して、それを回転させる操作と、反転させる操作を考えます。 まず、回転させる操作は、下図のように連結成分全体を $ 90 $ 度時計回りに回転させることを表します。 ``` ###. ##.# ..## #..# #.#. -> #### ###. ..#. ``` そして、反転させる操作は、下図のように連結成分全体を列方向か行方向に平行に反転させることを表します。 ``` ###. .### ..## ##.. #.#. -> .#.# ###. .### ###. ###. ..## #.#. #.#. -> ..## ###. ###. ``` $ A $ における集合の各要素を好きな回数回転するか反転させることで、 $ B $ におけるそれと一致させることができるか判定してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \vdots $ $ A_N $ $ B_1 $ $ B_2 $ $ \vdots $ $ B_N $

一致させることが可能なら `Yes` 、不可能なら `No` と出力してください。

### Sample Explanation 1 グリッド $ A $ と $ B $ にはそれぞれ次の `#` によって表される $ 3 $ つの連結成分が存在します。（下図はそれらを回転せずに平行移動させて並べたものです。） ``` ................ ..##....#....#.. ...#....#....... ................ ................ ...#....##...#.. ..##............ ................ ``` $ A $ の連結成分のうち、 - 左のものは回転操作を $ 2 $ 回行った後反転操作を $ 1 $ 回行うことで下に示す $ B $ の連結成分に一致させられます。 - 真ん中のものについては回転操作を $ 1 $ 回行うことで一致させられます。 - 右のものについては操作をせずとも一致しています。 よって、 連結成分の集合を一致させることが可能なので `Yes` を出力してください。 ### Sample Explanation 2 $ A $ における連結成分の内、下図に表している $ 2 $ つについては、下のように連結することで $ B $ の連結成分と一致させることができることができるように見えます。しかし、複数の連結成分を繋げて $ 1 $ つの連結成分として扱うことはできません。 ``` ........ ........ .###.... ...###.. .###..#. ..#.###. ...#..#. .....##. ..#...#. -> .##...#. -> .....##. -> .....##. .....##. ..#..... ......#. ......#. ........ ........ ........ ........ ``` ### Constraints - $ 1 \leq N, M \leq 1000 $ - $ A_i, B_i $ は `.` と `#` からなる長さ $ M $ の文字列 ( $ 1 \leq i \leq N $ ) - $ N, M $ は整数