Deciphering Characters

Decide whether two binary images represent the same character by comparing their connected components and the containment (surrounds) relations among them.

Medium7GraphBFSDFSImplementationNo attempts yetTime limit2sMemory limit512 MB

Problem

A syndicate of unknown origin left image data behind, and you have to analyze it. Its members wrote with characters they invented themselves. One binary image holds one character written in black ink on white paper.

Images that look different often stand for the same character. The surrounding relation between connected components decides whether two images stand for the same character. The definitions follow. Assume that white pixels fill the whole plane outside the given image.

  • White connected component: a set of white pixels connected to each other horizontally or vertically.
  • Black connected component: a set of black pixels connected to each other horizontally, vertically, or diagonally.
  • Connected component: a white connected component or a black connected component.
  • Background component: the connected component that holds the pixels outside the image. Every white pixel on the border of the image therefore belongs to the background component.
connecteddisconnected

Connectedness of white pixels.

connectedconnected

Connectedness of black pixels.

Let C1C_1 be a connected component of an image, and let C2C_2 be another connected component of the same image with the opposite color. Build a modified image in which every pixel that lies in neither C1C_1 nor C2C_2 takes the color of C2C_2. If neither C1C_1 nor C2C_2 is the background component, the pixels outside the image also take the color of C2C_2. When no pixel of C2C_2 belongs to the background component of the modified image, C1C_1 surrounds C2C_2 in the original image.

Two images stand for the same character when both of the following conditions hold.

  • The two images have the same number of connected components.
  • Let SS and SS' be the sets of connected components of the two images. A bijection f:SSf : S \to S' exists that satisfies the following conditions.
    • For each connected component CC in SS, f(C)f(C) has the same color as CC.
    • For each C1C_1 and C2C_2 in SS, f(C1)f(C_1) surrounds f(C2)f(C_2) if and only if C1C_1 surrounds C2C_2.

The connected components of the two images in the figure below have the following surrounding relations.

  • C1C_1 surrounds C2C_2.
  • C2C_2 surrounds C3C_3.
  • C2C_2 surrounds C4C_4.
  • C1C'_1 surrounds C2C'_2.
  • C2C'_2 surrounds C3C'_3.
  • C2C'_2 surrounds C4C'_4.

The bijection f(Ci)=Cif(C_i) = C'_i satisfies both conditions, so the two images stand for the same character.

Write a program that decides whether two given images stand for the same character.

Input

The input holds at most 200 datasets. A line with two zeros ends the input. Each dataset has this form.

image 1
image 2

Each image has this form.

h w
p(1,1) ... p(1,w)
...
p(h,1) ... p(h,w)

hh and ww are the height and the width of the image in pixels, and 1h1001 \le h \le 100 and 1w1001 \le w \le 100 hold. Each of the hh lines that follow holds exactly ww characters with no separator between them. p(y,x)p(y,x) is the color of the pixel in row yy from the top and column xx from the left. A period (".") means white and a sharp sign ("#") means black.

Output

For each dataset, print yes on one line when the two images stand for the same character, and print no otherwise. Print nothing else.