Koa 考拉有一个 $$$A$$$ 矩阵,包含 $$$n$$$ 行和 $$$m$$$ 列。该矩阵的元素是从 $$$1$$$ 到 $$$n \cdot m$$$ 的不同整数(从 $$$1$$$ 到 $$$n \cdot m$$$ 的每个数字在矩阵中只出现一次)。
对于 $$$n$$$ 行和 $$$m$$$ 列的任意矩阵 $$$M$$$,我们定义以下内容:
- $$$M$$$ 的第 $$$i$$$ 行定义为 $$$R_i(M) = [ M_{i1}, M_{i2}, \ldots, M_{im} ]$$$ 对于所有 $$$i$$$ ($$$1 \le i \le n$$$)。
- $$$M$$$ 的第 $$$j$$$ 列定义为 $$$C_j(M) = [ M_{1j}, M_{2j}, \ldots, M_{nj} ]$$$ 对于所有 $$$j$$$ ($$$1 \le j \le m$$$)。
Koa 将 $$$S(A) = (X, Y)$$$ 定义为 $$$A$$$ 的频谱,其中 $$$X$$$ 是 $$$A$$$ 行中最大值的集合,$$$Y$$$ 是 $$$A$$$ 列中最大值的集合。
更正式地说:
- $$$X = \{ \max(R_1(A)), \max(R_2(A)), \ldots, \max(R_n(A)) \}$$$
- $$$Y = \{ \max(C_1(A)), \max(C_2(A)), \ldots, \max(C_m(A)) \}$$$
Koa 要求你找到一些由 $$$n$$$ 行和 $$$m$$$ 列组成的矩阵 $$$A'$$$,使得从 $$$1$$$ 到 $$$n \cdot m$$$ 的每个数字在矩阵中恰好出现一次,并且满足以下条件:
- $$$S(A') = S(A)$$$
- $$$R_i(A')$$$ 对于所有 $$$i$$$ 都是双调的 ($$$1 \le i \le n$$$)
- $$$C_j(A')$$$ 对于所有 $$$j$$$ 都是双调的 ($$$1 \le j \le m$$$)
更正式地说:如果存在某个位置 $$$p$$$ ($$$1 \le p \le k$$$) 使得 $$$t_1 < t_2 < \ldots < t_p > t_{p+1} > \ldots > t_k$$$ ,则 $$$t$$$ 是双调的。
帮助Koa找到这样的矩阵或者确定它不存在。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 250$$$) — $$$A$$$ 的行数和列数。
以下 $$$n$$$ 行均包含 $$$m$$$ 整数。第 $$$i$$$ 行中的第 $$$j$$$ 整数表示矩阵 $$$A$$$ 的元素 $$$A_{ij}$$$ ($$$1 \le A_{ij} \le n \cdot m$$$)。保证从 $$$1$$$ 到 $$$n \cdot m$$$ 的每个数字在矩阵元素中恰好出现一次。
输出
如果这样的矩阵不存在,则在一行上打印$$$-1$$$。
否则,输出必须由 $$$n$$$ 行组成,每行由 $$$m$$$ 空格分隔的整数组成 - $$$A'$$$ 的描述。
第 $$$i$$$ 行中的第 $$$j$$$ 数字表示元素 $$$A'_{ij}$$$。
从 $$$1$$$ 到 $$$n \cdot m$$$ 的每个整数都应该在 $$$A'$$$ 中出现一次,$$$A'$$$ 中的每一行和每一列都必须是双调的,并且 $$$S(A) = S(A')$$$ 必须成立。
如果有很多答案,请打印任何答案。
示例
输入 #1
3 3 3 5 6 1 7 9 4 8 2
输出 #1
9 5 1 7 8 2 3 6 4
输入 #2
2 2 4 1 3 2
输出 #2
4 1 3 2
输入 #3
3 4 12 10 8 6 3 4 5 7 2 11 9 1
输出 #3
12 8 6 1 10 11 9 2 3 4 5 7
注意
让我们分析第一个样本:
对于矩阵 $$$A$$$ 我们有:
- $$$X = \{ \max(R_1(A)), \max(R_2(A)), \max(R_3(A)) \} = \{ 6, 9, 8 \}$$$
- $$$Y = \{ \max(C_1(A)), \max(C_2(A)), \max(C_3(A)) \} = \{ 4, 8, 9 \}$$$
- 所以 $$$S(A) = (X, Y) = (\{ 6, 9, 8 \}, \{ 4, 8, 9 \})$$$
对于矩阵 $$$A'$$$ 我们有:
- 请注意,每个数组都是双调的。
- $$$X = \{ \max(R_1(A')), \max(R_2(A')), \max(R_3(A')) \} = \{ 9, 8, 6 \}$$$
- $$$Y = \{ \max(C_1(A')), \max(C_2(A')), \max(C_3(A')) \} = \{ 9, 8, 4 \}$$$
- 所以 $$$S(A') = (X, Y) = (\{ 9, 8, 6 \}, \{ 9, 8, 4 \})$$$