← 返回题目列表

Codeforces · 1383/D

D. 重新排列

中文机器翻译题面 查看原题

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 \})$$$