题目描述

题目译自 $OOI$ $2016$ $Day$ $1$ $T4$《Сжатие таблицы / Table Compression》。

彼得对数据压缩算法产生了浓厚的兴趣。他已经学习了 $\textit{gz}$、$\textit{bz}$、$\textit{zip}$ 等多种格式。受到新知识的启发，彼得决定开发自己的压缩格式，并将其命名为 $\textit{dis}$。

彼得决定压缩表格。他有一个包含 $n$ 行 $m$ 列的表格，表格中填充了正整数。他希望将表格中元素的值替换为新的正整数，使得每行和每列中元素的相对关系保持不变。也就是说，如果在某一行中原始表格的 $a_{i,j} < a_{i,k}$，则压缩后的表格中 $a'_{i,j} < a'_{i,k}$；如果 $a_{i,j} = a_{i,k}$，则 $a'_{i,j} = a'_{i,k}$。同样地，如果在某一列中原始表格的 $a_{i,j} < a_{p,j}$，则压缩后的表格中 $a'_{i,j} < a'_{p,j}$；如果 $a_{i,j} = a_{p,j}$，则 $a'_{i,j} = a'_{p,j}$。

由于较大的数值需要更多的存储空间，因此压缩后表格中元素的最大值应尽可能小。

彼得在理论上是个专家，但他并不喜欢写代码。请帮助他实现 $\textit{dis}$ 压缩格式。

---

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m$ 且 $n \cdot m \leq 10^6$），分别表示表格的行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个整数 $a_{i,j}$ ($1 \leq a_{i,j} \leq 10^{9}$)，表示表格中元素的值。

---

输出格式

输出压缩后的表格：包含 $n$ 行，每行有 $m$ 个数字。

如果存在多个答案使得最大值最小，可以输出其中任意一个。

---

样例 $1$

输入

2 2
1 2
3 4

输出

1 2
2 3

在第一个样例中，$a_{1,2} \neq a_{2,1}$，但由于它们不在同一行或同一列中，压缩时可以将它们设置为相等。

---

样例 $2$

输入

4 3
20 10 30
50 40 30
50 60 70
90 80 70

输出

2 1 3
5 4 3
5 6 7
9 8 7

---

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	测试点编号	分值	附加限制	子任务依赖	备注
1	$3 \sim 19$	$10$	$n \leq 1000$，$m = 1$
2	$20 \sim 39$	$15$	$n, m \leq 100$，所有 $a_{i,j}$ 不同
3	$40 \sim 74$		$n, m \leq 100$	$0, 2$
4	$75 \sim 84$		$n, m \leq 400$，所有 $a_{i,j}$ 不同	$2$
5	$85 \sim 102$		$n, m \leq 400$	$0, 2, 3, 4$
6	$103 \sim 112$		所有 $a_{i,j}$ 不同	$2, 4$
7	$--$			$0 \sim 6$

---