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 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 $r$ and $c$.
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.
|Sample Input 1||Sample Output 1|
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