Little Petya 现在喜欢数据压缩算法。他已经研究过 gz、bz、zip 算法和许多其他算法。受到新知识的启发,Petya 现在正在开发新的压缩算法,他想将其命名为 dis。
Petya 决定压缩表。给他一个由 n 行和 m 列组成的表 a,其中填充有正整数。他想要构建由正整数组成的表a',使得每行和每列中元素的相对顺序保持相同。也就是说,如果在初始表 ai, j < ai, k 的某行 i 中,则在结果表中 a'i, j < a'i, k,并且如果 ai, j = ai, k 则 a'i, j = a'i, k。类似地,如果在初始表 ai, j < ap, j 的某个列 j 中,则在压缩表 a'i, j < a'p, j 中,如果 ai, j = ap, j 则 a'i, j = a'p, j。
因为大的值需要更多的空间来存储它们,所以a'中的最大值应该尽可能小。
Petya 理论上很好,但是,他需要你的帮助来实现算法。
输入
输入的第一行包含两个整数 n 和 m ($$1 \leqslant n, m \text{ 和 } n \cdot m \leqslant 1000000$$,分别是表的行数和列数。
以下 n 行中的每一行都包含 m 个整数 ai, j (1 ≤ ai, j ≤ 109),它们是表中的值。
输出
以 n 行的形式输出压缩表,每行包含 m 个整数。
如果存在多个答案,使得压缩表中的最大数量尽可能小,则允许输出其中任何一个。
示例
输入 #1
2 2 1 2 3 4
输出 #1
1 2 2 3
输入 #2
4 3 20 10 30 50 40 30 50 60 70 90 80 70
输出 #2
2 1 3 5 4 3 5 6 7 9 8 7
注意
在第一个样本测试中,尽管a1,2≠a21,但它们并不位于同一行或列,因此压缩后它们可能会变得相等。