题目描述

题目译自 Open Olympiad in Informatics 2016 Day1 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 1000000$），分别表示表格的行数和列数。

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

输出格式

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

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

2 2
1 2
3 4

1 2
2 3

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

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$ 是样例。