DMOPC '21 Contest 7 P1 - Chika Grids

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

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 N \times M 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?

Constraints

1 \le N, M \le 1\,500

0 \le a_{i,j} \le 10^9

Subtask 1 [10%]

N = 1

a_{i,j} = 0

Subtask 2 [20%]

a_{i,j} = 0

Subtask 3 [30%]

N = 1

Subtask 4 [40%]

No additional constraints.

Input Specification

The first line contains 2 integers N and M.

The next N lines each contain M integers a_{i,j}, representing the cells of the grid. If a_{i,j} = 0, the cell is currently empty.

Output Specification

If it is impossible to satisfy the challenge, output -1 on a line by itself.

Otherwise, output an N \times M 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 10^{18}.

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

-1

Comments


  • 0
    John  commented on April 21, 2022, 2:45 p.m.

    The best anime...