Slink

Slitherlink is a loop puzzle popularized by the Japanese publisher Nikoli, the same company that made Sudoku famous. The rules are easy to state, but the puzzles can be hard to solve.

A puzzle is a rectangular grid of dots that forms a set of cells. Each cell is either blank or holds an integer from $0$ to $3$. You must connect neighboring dots with horizontal and vertical unit segments so that the drawn segments form a single closed loop (a connected cycle in which every dot has exactly two incident segments, or none at all). Every numbered cell must be touched by exactly as many of its four sides as its number; a blank cell may be touched by any number of sides. A well-formed puzzle contains enough numbers to force a unique loop.

It has been shown (by Takayuki Yato at the University of Tokyo) that solving general Slitherlink is NP-complete, meaning no efficient algorithm is known for the general case. With one restriction, however, the puzzles become tractable in practice. The puzzle in this problem, called Slink, is Slitherlink with no blank cells: every cell carries a number telling exactly how many of its four sides belong to the loop. The solution loop of a Slink puzzle is identical to that of the corresponding Slitherlink; only the amount of given information differs.

Slink puzzles can be solved by repeatedly applying local deduction rules. For example, every side of a cell marked $0$ is definitely absent from the loop. And a $3$ next to a $0$ must use the three sides it does not share with the $0$: the shared side is eliminated by the $0$, leaving exactly three possible sides for the $3$, all of which must therefore be used.

The deduction rules are listed below. Each rule either forces a side into the loop or forces it out. Every input puzzle is guaranteed to have a unique solution that can be reached by always applying a rule whenever it applies.

1. Zero: every side of a cell containing $0$ is excluded from the loop.
2. Count completed: if a cell shows $n$ and exactly $n$ of its sides are already in the loop, its remaining sides are excluded.
3. Count forced: if a cell shows $n$ and only $n$ of its sides are still possible (the rest already excluded), those remaining sides are all included.
4. Adjacent threes: if two $3$ cells share a side, that shared side and the two outer sides parallel to it are all included.
5. Diagonal threes: if two $3$ cells touch at only a single corner (diagonally adjacent), the two outer sides at the corners farthest apart are included.
6. Forced turn: if a segment already enters a dot and only one other side at that dot is still possible, that side is included.
7. Full dot: if a dot already has two incident sides in the loop, its remaining sides are excluded.
8. Dead dot: if three of a dot's sides are excluded, the fourth is excluded as well (a dot always has degree $0$ or $2$, never $1$).
9. Blocked three (corner): a $3$ that has two sides blocked at one dot (for instance in a corner of the puzzle) must include the two sides meeting at that dot.
10. Two with a blocked corner: for a $2$, if both sides at one of its corners are blocked and one side at an adjacent corner of the $2$ is also blocked, the other side at that adjacent corner is included.
11. Blocked one (corner): a $1$ whose two sides at one dot are both blocked (for instance in a corner of the puzzle) forces the other two sides at that dot to be excluded.
12. Three entered at a corner: if the loop reaches a corner of a $3$ and the side leaving the $3$ outward at that same corner is blocked, then the two sides of the $3$ at the opposite corner are included.
13. Diagonal three and one: if a $3$ and a $1$ touch at only a single corner and the outward sides at the corner of the $3$ farthest from the $1$ are blocked, then the sides at the far corner of the $1$ are blocked as well; the converse also holds.
14. Two entered at a corner: if the loop reaches a corner of a $2$ and the outward side there is blocked, and one outward side at the diagonally opposite corner is also blocked, then the other outward side at that opposite corner is included.
15. One entered at a corner: if the loop reaches a corner of a $1$ and the side leaving the $1$ outward at that same corner is blocked, then the two sides of the $1$ at the opposite corner are excluded.

The input contains a sequence of Slink puzzles.

Each puzzle begins with a line containing two integers $r$ and $c$ (the number of rows and columns of cells), separated by a space. The next $r$ lines each contain $c$ integers from $0$ to $3$, separated by spaces, giving the number in every cell.

Puzzle sizes range from $2 \times 2$ up to $20 \times 20$ cells. Every puzzle is guaranteed to have a unique solution that can be found by always applying a deduction rule whenever one applies.

A line containing 0 0 marks the end of the input and is not a puzzle.

For each puzzle, first print the puzzle number on a line by itself (the first puzzle is $1$, the second is $2$, and so on). Then print a picture of the puzzle's unique solution.

Draw the solution with these characters: a vertical side of the loop is a vertical bar |, a horizontal side is a run of dashes -, a dot where the loop changes direction is a plus sign +, and every cell number is printed with one blank space to its left and one to its right. A dot where the loop passes straight through is drawn as part of the line it lies on.

Surround the whole picture with a border of hash marks #, positioned so that the number in the top-left cell sits four columns to the right of the border and three rows below it, and the number in the bottom-right cell sits four columns to the left of the border and three rows above it. Follow the exact format of the examples.