The Eight Puzzle, among other sliding-tile puzzles, is one of the famous problems in artificial intelligence. Along with chess, tic-tac-toe and backgammon, it has been used to study search algorithms.The Eight Puzzle can be generalized into an *M* × *N* Puzzle where at least one of *M* and *N* is odd. The puzzle is constructed with *MN* − 1 sliding tiles with each a number from 1 to *MN* − 1 on it packed into a *M* by *N* frame with one tile missing. For example, with *M* = 4 and *N* = 3, a puzzle may look like:

1 | 6 | 2 |

4 | 0 | 3 |

7 | 5 | 9 |

10 | 8 | 11 |

The input consists of multiple test cases. Each test case starts with a line containing *M* and *N* (2 ≤ *M*, *N* ≤ 999). This line is followed by *M* lines containing *N* numbers each describing an *M* × *N* puzzle.The input ends with a pair of zeroes which should not be processed.

提交代码