Fantasmagorie

Émile's dreams often feature people or animals who become distorted into others. Émile would like to show the enchanting world of his dreams to everybody by creating the very first animated cartoon, in black and white of course. After waking up, Émile only remembers the initial and final forms appearing in his dream, not the transformation itself, so he is asking you to reproduce these "morphings" by detailing the steps taken for transforming the first image into the second.

Émile's images respect three constraints. First, all pixels on the border of the image, meaning the leftmost and rightmost columns and the top and bottom rows, have the same color. Second, the image does not contain any $2 \times 2$ square of the form or .

The third constraint is as follows. Subdivide the image into regions, which are the connected monochromatic areas of the image. That is, regions form the finest partition of the pixels such that any two adjacent pixels of the same color are in the same region. Two regions are adjacent if they contain adjacent pixels. In Émile's images, every region is adjacent to at most two other regions, and the region containing the border pixels is adjacent to at most one other region.

You are given two black and white images of the same size $W \times H$. Your goal is to find a "morphing" that transforms the first image into the second one. A morphing from image $A$ to image $B$ is a sequence of images starting with $A$ and ending with $B$ such that:

• each image (except the first) can be obtained from the previous one by flipping one bit;
• each image respects the three constraints above;
• the number of regions of each color does not change during the morphing.

The first line contains two space-separated integers $W$ and $H$. Then come $H$ lines that describe the first image row by row, from top to bottom. Each line is composed of $W$ characters describing the row's pixels from left to right: the $k$-th character is '.' if the $k$-th pixel of the row is white, and '#' if it is black. Finally come $H$ lines that describe the second image in the same format.

If no morphing exists, print the word "IMPOSSIBLE" on a single line. Otherwise, describe one possible morphing. If the $(k+1)$-th image is obtained from the $k$-th image by flipping the pixel in column $c$ and row $r$ (with $0 \le c < W$ and $0 \le r < H$, where $c = 0$ is the leftmost column and $r = 0$ is the topmost row), the $k$-th output line contains the pair $(c,r)$.

• $1 \le H \le 64$
• $1 \le W \le 103$
• The first and last images are distinct.
• The output contains at most $250\,000$ pixel flips.