You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

小 $y$ 现在对数据压缩算法情有独钟。她已经学习了 $gz$、$bz$、$zip$ 算法和许多其他算法。受新知识的启发，小$y$ 正在开发新的压缩算法，并将其命名为 $dis$。

小$y$ 决定压缩表格。她得到了一个由 $n$ 行和 $m$ 列组成的表 $a$，该表填充的是正整数。她想建立一个由正整数组成的表 $a'$，使每行和每列中元素的相对顺序保持不变。也就是说，如果初始表的某一行 $i$ 中有 $a_{i,j} < a_{i,k}$，那么生成表中就有 $a'_{i,j} < a'_{i,k}$，如果有 $a_{i,j} = a_{i,k}$，那么生成表中就有 $a'_{i,j} = a'_{i,k}$。同样，如果初始表的某列 $j$ 中有 $a_{i,j} < a_{p,j}$ ，那么压缩表中有 $a'_{i,j} < a'_{p,j}$，如果有 $a_{i,j} = a_{p,j}$，那么有 $a'_{i,j} = a'_{p,j}$。

由于大值需要更多空间来存储，因此 $a'$ 中的最大值应尽可能小。

小$y$ 的理论很好，但她需要你的帮助来实现算法。

Format

Input

输入的第一行包含两个整数 $n$ 和 $m$ （$1 \le n, m$ 且 $n \times m \le 1\,000\,000$），分别是表格的行数和列数。
接下来 $n$ 行，每行包含 $m$ 个整数 $a_{i,j}$（$1 \le a_{i,j} \le 10^9$），表示表格中的值。

Output

以 $n$ 行的形式输出压缩表，每行包含 $m$ 个整数。 如果存在多个答案，而压缩表中的最大数字是可能的最小值，则允许输出其中任何一个答案。

Samples

2 2
1 2
3 4

1 2
2 3

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