407403: GYM102784 J Jackie's Jack-O'-Lanterns

J. Jackie's Jack-O'-Lanternstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Each year in the middle of October, Jackie hosts a fabulous pumpkin carving contest. Participants from all across the neighborhood bring their elaborate jack-o'-lanterns to Jackie for her to judge and pick a winner. Of course, the jack-o'-lanterns in Jackie's contest are no ordinary jack-o'-lanterns. In fact, these carved pumpkins don't just have holes carved into them, but they can have floating pumpkin pieces inside of the carved holes, held up by magic (or perhaps conveniently placed toothpicks) such that the holes appear like dark rings. Further, these floating pumpkin pieces could be carved with holes that themselves could contain floating pumpkin pieces and so on!

Now Jackie takes this contest very seriously and wants to make sure that each submitted jack-o'-lantern is entirely unique. She will not tolerate even remote plagiarism! Thus Jackie demands that each jack-o'-lantern represent a unique pumpkin topology. Jackie defines a pumpkin topology to be the set of hierarchical relations between pumpkin pieces and embedded holes where both pumpkin pieces and holes are considered as distinct components in the topology. For instance, there may be several holes cut within the outer uncut pumpkin, and each distinct hole would be considered a descendant of the outer pumpkin flesh. Then, perhaps within one of these holes there might be one or several embedded floating pumpkin pieces, which would each be considered a descendant of the surrounding hole. Further within one of these pumpkin pieces could be other embedded holes which are descendants of the surrounding piece, etc.

The carved-hole shapes and sizes can vary, but Jackie only cares about ensuring that no two jack-o'-lanterns share the same pumpkin topology. Given the appearance of two jack-o'-lanterns, help Jackie enforce her contest rules.

Input

The first line of input contains two integers, $$$R$$$ and $$$C$$$ ($$$3 \leq R, C \leq 150$$$), the dimension of the carved pumpkins in rows and columns respectively. Next, $$$R$$$ lines follow, each containing $$$C$$$ characters which are each either '#' to indicate a hole space or '.' to indicate pumpkin flesh. These lines describe the first jack-o'-lantern. Next follows a blank line for visual spacing, and after that, in the same format as the first jack-o'-lantern description, another $$$R$$$ lines follow which represent the second jack-o'-lantern that Jackie is comparing.

Note that the first and last rows and columns of each jack-o'-lantern will be filled with '.' or pumpkin flesh. Every hole or pumpkin piece will be surrounded entirely by only one parent pumpkin piece or hole respectively. Two character's both representing either pumpkin flesh or hole spaces are considered adjacent and thus connected as part of the same topological unit if they are directly above, below, or beside one another (not diagonally).

Output

Print 'YES' (without quotes) if the jack-o'-lanterns share the same topology and 'NO' otherwise.

ExamplesInput

10 15
...............
.#####...#####.
.#...#...#...#.
.#####...#####.
......###......
.###.......###.
.#.#########.#.
.#..#..#..#..#.
.#############.
...............

...............
.###..####.###.
.#.#..##...#.#.
.###...##..###.
.#.#...........
.#####....####.
.#.#.#....#.##.
.#####....#..#.
..........####.
...............

Output

YES

Input

10 15
...............
.#####...#####.
.#...#...#...#.
.#####...#####.
......###......
.###.......###.
.#.#########.#.
.#..#..#..#..#.
.#############.
...............

...............
.#####...#####.
.#...#...#.#.#.
.#####...#####.
......###......
.###.......###.
.#.#########.#.
.#...........#.
.#############.
...............

Output

NO

Note

In the first sample case, the two given pumpkins are topologically equivalent, sharing the topology represented by the tree below, where white nodes denote pumpkin flesh pieces and black nodes denote carved holes. The white root of the tree represents the outer pumpkin flesh. The two black "eye" holes of the first jack-o'-lantern are represented by the black nodes with one child each. The "nose" hole is represented by the black node with no children. Then the "mouth" hole containing four "teeth" pumpkin pieces is represented by the black node with four children pieces. Note that the second, more abstract pumpkin in this sample case contains the same hierarchically-ordered components.

In the second sample case, the second given jack-o'-lantern is not topologically equivalent to the first but instead bears the topology represented by this tree below. Note that it is a somewhat similar and would be topologically equivalent to the tree represented above if the black node containing two children below actually contained four instead.