矩阵最大字典序

题目描述

给定一个大小为 $n \times m$ 的矩阵 $A$，其第 $i$ 行第 $j$ 列的元素记为 $A_{i,j}$。

你可以对矩阵进行任意次下述操作：

• 选择两个不相邻的元素进行交换。
• 形式化地，选择两个坐标 $(i_1, j_1)$ 和 $(i_2, j_2)$，它们必须满足曼哈顿距离 $|i_1 - i_2| + |j_1 - j_2| \neq 1$。然后交换这两个位置的元素值。

你的任务是，通过任意次操作，使得最终得到的矩阵的字典序最大。

一个矩阵 $B$ 的字典序大于另一个矩阵 $C$，当且仅当将两个矩阵按行优先展开成一维序列后（即 $B_{1,1}, B_{1,2}, \dots, B_{1,m}, B_{2,1}, \dots, B_{n,m}$），序列 $B$ 的字典序大于序列 $C$。

输入格式

第一行包含两个正整数 $n, m$，表示矩阵的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个整数，表示矩阵 $A$ 的元素 $A_{i,j}$。

输出格式

输出 $n$ 行 $m$ 列，表示经过操作后能够得到的字典序最大的矩阵。每行的整数之间用一个空格隔开。

样例

样例输入

2 3
1 2 3
4 5 6

样例输出

6 5 4
3 2 1

提示

数据范围与约定

对于 $100\%$ 的数据，保证 $2 \le n, m \le 500$，且 $1 \le A_{i,j} \le 10^9$。