표 압축

어린 페탸는 데이터 압축 알고리즘을 좋아한다. 그는 gz, bz, zip 등 여러 알고리즘을 이미 공부했고, 그 지식을 바탕으로 dis라는 새 압축 알고리즘을 개발하고 있다.

페탸는 표를 압축하기로 했다. 양의 정수로 채워진 $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'$의 최댓값은 가능한 한 작아야 한다.

첫 줄에 표의 행 수 $n$과 열 수 $m$이 주어진다 ($1 \le n, m$이고 $n \cdot m \le 1\,000\,000$).

이어지는 $n$개의 줄에는 각각 $m$개의 정수 $a_{i,j}$ ($1 \le a_{i,j} \le 10^{9}$)가 주어진다. 표의 값이다.

압축된 표를 $n$개의 줄로 출력하며, 각 줄에는 $m$개의 정수를 출력한다.

압축된 표의 최댓값을 최소로 만드는 답이 여럿이면 그중 아무거나 출력해도 된다.

첫 번째 샘플에서 $a_{1,2} \ne a_{2,1}$이다. 두 원소는 같은 행이나 같은 열에 있지 않으므로 압축 후에 같은 값이 될 수 있다.