Alice often plays chess. Moreover, since she loves to travel to other galaxies, she knows many varieties of this ancient game. Sometimes she just solves puzzles created on the chessboard. Alice's chessboard can have a variety of sizes, not just 8×8.
Now Alice is solving the following chess puzzle, the essence of which is as follows. A positive integer is written on one of the fields of the board with size m×n and then a queen is placed on it. After that, the queen makes k moves . The queen moves according to standard chess rules. The queen cannot move to squares that he has already been to. Also, before making a move, an integer is written on the selected field, and such that it is greater than all other numbers already written on the board.
The solution to the puzzle is to reconstruct the route of the queen using the numbers written on the board. Perhaps the written numbers do not give a solution.
To solve this puzzle, Alice wrote a program that can solve quickly for large values m, n and k.
Write such a program.
In standard chess rules, the queen can move to any field of the board that is on the same vertical, horizontal or diagonal with the field on which it is located.
Input
The first line contains numbers
m,
n and
k ( 1< = m, n <= 300, 0 <= k < mn). The following
m lines each contain
k integers and describe board fields (an empty field corresponds to a number
0, and a field on which the number – is written). All numbers written on the board are positive, integer and do not exceed 10
9.
Output
If the puzzle is made with a mistake and the numbers written on it do not give a solution, then print «
Wrong Board».
Otherwise, output
m line by
n numbers – for each field print the number of the move before which the queen visited this field, and for the last field where it appeared – number
k + 1. For fields where the queen did not land, print the number
0.
Examples
| # |
Input |
Output |
| 1 |
4 4 7
10 20 0 100
30 0 0 40
0 0 0 0
45 42 0 70
|
1 2 0 8
3 0 0 4
0 0 0 0
6 5 0 7
|
| 2 |
2 4 4
10 20 30 40
0 50 0 0
|
Wrong Board
|
| 3 |
2 2 2
12
4 3
|
Wrong Board
|