It is well known that Chika loves puzzles. She has recently discovered a new puzzle, and is convinced it contains some hidden meaning.
Chika's puzzle is an grid. Some cells have already been filled in with positive integers. The challenge of the puzzle is to fill in the grid such that every row is sorted in strictly increasing order from left to right, and every column is sorted in strictly increasing order from top to bottom.
Chika is an expert at solving puzzles of course, it just happens that she can't solve this one, so she pawns it on you. Can you do it?
Subtask 1 [10%]
Subtask 2 [20%]
Subtask 3 [30%]
Subtask 4 [40%]
No additional constraints.
The first line contains integers and .
The next lines each contain integers , representing the cells of the grid. If , the cell is currently empty.
If it is impossible to satisfy the challenge, output
-1 on a line by itself.
Otherwise, output an grid of integers that satisfies the challenge. You cannot change any cells that have been already filled in. Each integer must be positive and be at most .
If there are multiple possible outputs, you may output any of them.
Sample Input 1
2 4 0 2 9 0 6 0 0 40
Sample Output 1
1 2 9 30 6 14 28 40
Sample Input 2
3 3 0 0 5 0 2 9 0 3 11
Sample Output 2