Double Vision

A company designs inks and fonts that can be read easily by both humans and machines. The fonts are laid out on a rectangular grid. Below is a simple 5×3 design for the first five digits.

. o .     . o .    oo .    oo .    o . o
o . o    . o .    . . o    . . o    o . o
o . o    . o .    . o .    oo .    ooo
o . o    . o .    o . .    . . o    . . o
. o .     . o .    ooo    oo .    . . o

The ink looks like ordinary black ink, but just below the surface the company adds a special polymer that an infrared scanner can detect. A human sees the black ink but not the polymer, while a machine sees the polymer but not the black ink. The polymer is far more expensive than the ink, so the company wants to use as little of it as possible. They have found that in many fonts every symbol can be uniquely identified by at most two pixels. By adding polymer to only one or two pixels per symbol, they sharply cut costs while keeping their scanners 100% accurate. The font above has this property; the pixels that uniquely identify each symbol are marked with #. (Other choices would also work.)

. # .     . o .    #o .    oo .    o . #
# . o    . # .    . . o    . . o    o . o
o . o    . o .    . o .    #o .    ooo
o . o    . o .    # . .    . . o    . . o
. o .     . o .    ooo    #o .    . . o

Write a program that decides whether a given font has this property, and if it does, marks the identifying pixels.

The input contains one or more test cases, followed by a line containing 0 0 0 (three zeros) that marks the end of the input.

Each test case starts with a line containing three positive integers n, r, and c separated by spaces: n is the number of symbols in the font, r is the number of rows in each grid, and c is the number of columns in each grid. The next r lines hold the images of the symbols in exactly the format shown: a dot . is an empty cell, a lowercase o is a pixel, and adjacent grids are separated by a single space. Each of these lines is at most 79 characters wide (not counting the end-of-line character), and r is at most 10. Test cases are numbered starting from 1.

For test case i, first print a line Test i. Then decide whether every symbol can be uniquely identified by one or two pixels. If some symbol cannot, print a line containing the single word impossible. Otherwise, print the font in the same format, except that the identifying pixels of each symbol are replaced with #.

In general several pixels or pixel pairs may uniquely identify a symbol, so the following rules make the answer unique. When comparing two pixels, the topmost-leftmost pixel is the one nearer the top of the grid; if both lie on the same row, it is the one nearer the left.

• If a single pixel works, mark the topmost-leftmost pixel that works.
• Never use a two-pixel solution when a one-pixel solution exists.
• If two pixels are needed, choose the pair whose first pixel is as topmost-leftmost as possible; among pairs that share that first pixel, choose the one whose second pixel is topmost-leftmost.

A pixel uniquely identifies a symbol when no other symbol has a pixel at the same position; a pair of pixels does so when no other symbol has a pixel at both positions.