Image Compression

Time limit1sMemory limit128 MB

Summary

Compress a binary square bitmap with a quadtree and a majority threshold, then output the image the encoding reconstructs.

Level: Medium4 of 10
Topics: Divide and conquer, Recursion, Matrix, Simulation
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples6

Example 1

Input

Expected output

Example 2
Input
```
2 75
01
10
0
```
Expected output
```
Image 1:
01
10
```
Example 3
Input
```
2 100
11
11
0
```
Expected output
```
Image 1:
11
11
```
Example 4
Input
```
1 51
1
0
```
Expected output
```
Image 1:
1
```

Example 5

Input

Expected output

Image 1:
1111
1111
0000
0000

Example 6

Input

Expected output

Image 1:
0
Image 2:
11
00
Image 3:
1111
1111
1111
1111