Codeforces Round 659 (Div. 1) |
---|
Finished |
Koa the Koala has a matrix $$$A$$$ of $$$n$$$ rows and $$$m$$$ columns. Elements of this matrix are distinct integers from $$$1$$$ to $$$n \cdot m$$$ (each number from $$$1$$$ to $$$n \cdot m$$$ appears exactly once in the matrix).
For any matrix $$$M$$$ of $$$n$$$ rows and $$$m$$$ columns let's define the following:
Koa defines $$$S(A) = (X, Y)$$$ as the spectrum of $$$A$$$, where $$$X$$$ is the set of the maximum values in rows of $$$A$$$ and $$$Y$$$ is the set of the maximum values in columns of $$$A$$$.
More formally:
Koa asks you to find some matrix $$$A'$$$ of $$$n$$$ rows and $$$m$$$ columns, such that each number from $$$1$$$ to $$$n \cdot m$$$ appears exactly once in the matrix, and the following conditions hold:
More formally: $$$t$$$ is bitonic if there exists some position $$$p$$$ ($$$1 \le p \le k$$$) such that: $$$t_1 < t_2 < \ldots < t_p > t_{p+1} > \ldots > t_k$$$.
Help Koa to find such matrix or to determine that it doesn't exist.
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 250$$$) — the number of rows and columns of $$$A$$$.
Each of the ollowing $$$n$$$ lines contains $$$m$$$ integers. The $$$j$$$-th integer in the $$$i$$$-th line denotes element $$$A_{ij}$$$ ($$$1 \le A_{ij} \le n \cdot m$$$) of matrix $$$A$$$. It is guaranteed that every number from $$$1$$$ to $$$n \cdot m$$$ appears exactly once among elements of the matrix.
If such matrix doesn't exist, print $$$-1$$$ on a single line.
Otherwise, the output must consist of $$$n$$$ lines, each one consisting of $$$m$$$ space separated integers — a description of $$$A'$$$.
The $$$j$$$-th number in the $$$i$$$-th line represents the element $$$A'_{ij}$$$.
Every integer from $$$1$$$ to $$$n \cdot m$$$ should appear exactly once in $$$A'$$$, every row and column in $$$A'$$$ must be bitonic and $$$S(A) = S(A')$$$ must hold.
If there are many answers print any.
3 3 3 5 6 1 7 9 4 8 2
9 5 1 7 8 2 3 6 4
2 2 4 1 3 2
4 1 3 2
3 4 12 10 8 6 3 4 5 7 2 11 9 1
12 8 6 1 10 11 9 2 3 4 5 7
Let's analyze the first sample:
For matrix $$$A$$$ we have:
For matrix $$$A'$$$ we have:
Name |
---|