← 返回题目列表

Codeforces · 650/C

C. 表压缩

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

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,但它们并不位于同一行或列,因此压缩后它们可能会变得相等。