核心结论与思路

1) 什么时候能实现任意排列？

若能把任意一对相邻位置（共享边）完成交换，我们就能用相邻交换生成任意排列，从而把所有元素整体按降序放入矩阵（行优先）即为最优。

对一对相邻格子 $(x_1,y_1)$、$(x_2,y_2)$，若存在某个“缓冲格” $t$，使得 $t$ 与两者都不相邻，则用三步实现相邻交换：

$(x_1\!\leftrightarrow\! t),\$ $(x_2\!\leftrightarrow\! t),\$

题目内容

小红给定一个大小为 $n×m$ 的矩阵 $A$ ，从上往下为第 $i$ 行，从左往右为第 $j$ 列，其所在元素为 $A_{ij}$ 。

每次操作可以选择两个不相邻的元素交换，形式化的，即选定两个坐标 $(i_1,j_1),(i_2,j_2)$ 满足 $|i_1 - i_2|+ |j_1- j_2|≠ 1$ ，然后交换 $A_{i_1,j_1}$和 $A_{i_2,j_2}$ 的元素值。

现在小红想要知道在所有操作结果中，矩阵字典序最大的元素分布。

矩阵字典序：两个大小为 $n×m$ 的矩阵 $p、q$ ，依次从第 $1$ 行到第 $n$ 行，第 $1$ 列到第 $m$ 列比较，当某个位置 $p_{i,j}> q_{i,j}$ ，则 $p$ 的矩阵字典序大于 $q$ ，若 $p_{i,j}< q_{i,j}$ ,则 $p$ 的矩阵字典序小于 $q$，若相等则继续比较，若比较到最后矩阵完全一致，则两个矩阵的字典序相等。

输入描述

第一行两个整数 $n,m(2 ≦ n,m ≤ 500)$ ，表示矩阵行列的大小。

接下来 $n$ 行，每行 $m$ 个元素，为矩阵 $A$ 的元素，其中 $1 ≤ A_{i,j} ≦ 10^9$ 。

输出描述

$n$ 行 $m$ 列，表示在所有操作结果中，矩阵字典序最大的元素分布。

样例1

输入

2 3
1 2 3
4 5 6

输出

6 5 4
3 2 1