Fantasmagorie

Émile's dreams often feature people or animals morphing into others. Émile would like to show everyone the enchanting world of his dreams 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's asking you to reproduce these "morphings" by detailing the steps taken to transform the first image into the second.

The images in Émile's dreams are not just any black-and-white images; they obey the following three constraints.

First, all pixels on the border of the image — 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

The third constraint is more complex and can be described as follows. Partition the image into regions, where a region is a connected monochromatic area — that is, the finest partition such that any two adjacent pixels of the same color are in the same region. Two regions are considered 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, and your goal is to find a "morphing" transforming 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.