Image Compression

Many two-dimensional image compression strategies rely on locating large regions of high similarity. This problem explores one such approach based on a hierarchical (quadtree) decomposition of a bitmap image. Every pixel is one of two colors, written as 0 (white) and 1 (black).

The image is encoded as a tree whose root represents the entire square region. If a region is monochromatic (every pixel the same color), the node for that region is a leaf that stores the region's color. Otherwise the region is split into four equal quadrants about its center, and the same procedure is applied recursively to each quadrant.

This lossless scheme becomes a lossy one with a single change. Instead of decomposing a region until it is perfectly monochromatic, fix an integer threshold $T$ (a percentage). A region becomes a leaf as soon as at least $T%$ of its pixels share one color, and that majority color is stored in the leaf; only when neither color reaches $T%$ is the region split into quadrants and processed recursively. A single-pixel region is always 100% one color, so the process always terminates.

To decompress (reconstruct) the image from such an encoding, every leaf region is filled entirely with its stored color.

Given an original bitmap and a threshold, output the image that results from compressing it with this lossy scheme and then decompressing it.

Because $T$ is at least 51, at most one color can ever reach the threshold, so the leaf's color is never ambiguous.

The input consists of a series of data sets, followed by a line containing only a single 0.

Each data set begins with a line containing two integers $W$ and $T$: $W$ is the width of the bitmap and $T$ is the threshold percentage. Every image is square, and $W$ is a power of two with $1 \le W \le 64$. The threshold satisfies $51 \le T \le 100$.

The line with $W$ and $T$ is followed by $W$ lines, each a string of exactly $W$ characters, each character either 0 or 1, giving one row of the bitmap from top to bottom.

For each data set, first print a line of the form Image k:, numbering the data sets starting from 1. Then print $W$ lines, each a string of 0 and 1 characters giving one row of the reconstructed bitmap, from top to bottom.