Nurikabe

Write a program that solves Nurikabe puzzles.

Nurikabe is played on a rectangular grid. Each cell is either empty (shown as .) or contains a single-digit number. To solve the puzzle you must color every cell either white (land) or black (sea) so that all of the following conditions hold. An island is a maximal group of white cells connected horizontally or vertically.

1. All black cells must be connected to one another.
2. Every numbered cell must belong to some island.
3. The number of white cells in each island must equal the number written in that island.
4. Every island must contain exactly one numbered cell.
5. No two different islands may be adjacent (connected) to each other.
6. No $2 \times 2$ area may be entirely black.

Cells are considered adjacent only horizontally or vertically, never diagonally. Every input is guaranteed to have a unique solution.

The input consists of several test cases.

The first line of each test case contains the puzzle dimensions $n$ and $m$, separated by a space. ($3 \le n, m \le 9$)

Each of the next $n$ lines describes the initial state of the puzzle. Each line has $m$ characters: an empty cell is given as ., and a numbered cell is given as its digit. Every number is a single digit.

The last line of the input contains two zeros, marking the end of the input.

For each test case, print the solved puzzle. Print each black cell as #, and print each white cell as its original character (. or its digit). Print one blank line between the outputs of consecutive puzzles.