Problem E
Block Crusher

You are responsible for testing the compressive strength of various composite materials. You take a rectangular block, crush it from the sides and see where it beaks. This is hard work, and it’s dirty, so you decide to write a simulator to get yourself some help.

Computationally, you model a block as being composed of a grid square regions of materials of various strengths. You model the strength of a square as an integer between $1$ and $9$. When sufficient force is applied from the sides, the block will shatter along a fracture line. The fracture line is a path through the squares that starts in a square along the top edge of the block and ends in a square along the bottom edge. Among all such paths, the fracture line is the one that minimizes the total strength (i.e., the sum of the strength values) of all the squares on the path. The fracture line can travel from square to square up, down, left, right or diagonally as it goes from the top edge to the bottom edge.

Input

Input consists of up to $200$ block descriptions. Each block description starts with a line containing two integers, $1 \le h \le 20$ and $1 \le w \le 60$, giving the height and width of the block. This is followed by $h$ lines of $w$ digits each, where each digit is in the range $1 \ldots 9$. The end of all block descriptions is marked by values of zero for $h$ and $w$.

Output

For each block, print a copy of the block with the digits along its fracture line replaced by spaces. There will only be one fracture line that has the minimum strength. Print a blank line after each block.

3 7
2281431
2329463
7183839
7 6
517135
935519
731353
375951
575195
579573
359739
0 0

228 431
23 9463
7 83839

517 35
9355 9
73135 
37595 
57519 
57957 
3597 9