朵拉非常喜欢冒险。在一次旅行中,她遇到了一座神奇的城市,它由东边的$$$n$$$街道和南边的$$$m$$$街道组成。当然,这个城市有 $$$nm$$$ 十字路口。在第$$$i$$$东街和第$$$j$$$南街的任何交叉路口都有一座巨大的摩天大楼。朵拉立刻产生了好奇心,决定去探索城市建筑的高处。
当朵拉穿过第 $$$i$$$ 东街和第 $$$j$$$ 南街的交叉路口时,她检查了这两条街道。当朵拉得知这两条街上所有摩天大楼的高度后,她想知道:如何重新分配这两条街上摩天大楼的高度,使得最大高度尽可能小,并且比较一条街上任意两座摩天大楼的高度的结果不会改变。
形式上,在每个 $$$nm$$$ 交叉点上,Dora 都解决了一个独立的问题。她看到 $$$n + m - 1$$$ 摩天大楼,并且对于每座摩天大楼,她都知道其真实高度。此外,可以比较任意两个高度以获得“更大”、“更小”或“等于”的结果。现在,Dora 想要选择一些整数 $$$x$$$ 并为每个摩天大楼分配一个从 $$$1$$$ 到 $$$x$$$ 的高度。在指定高度时,Dora 希望保留两条街道上摩天大楼的相对顺序。也就是说,当前东街两座摩天大楼的高度比较结果不应改变,当前南街两座摩天大楼高度比较的结果也不应改变。请注意,位于南街的摩天大楼不与仅位于东街的摩天大楼进行比较。然而,位于街道交叉口的摩天大楼可以与南部和东部的摩天大楼进行比较。对于每个交叉点,Dora 想要独立计算可能的最小 $$$x$$$。
例如,如果交叉路口及其对应的两条街道如下所示:
那么最好按如下方式替换摩天大楼的高度(请注意,保留东部街道内和南部街道内的所有比较“小于”、“等于”、“更大”)
最大的使用数字是 $$$5$$$,因此这个交集的答案将是 $$$5$$$。
帮助朵拉计算每个交叉路口的答案。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 1000$$$) – 向东的街道数量和向南的街道数量。
以下 $$$n$$$ 行中的每一行都包含 $$$m$$$ 整数 $$$a_{i,1}$$$、$$$a_{i,2}$$$、...、$$$a_{i,m}$$$ ($$$1 \le a_{i,j} \le 10^9$$$)。位于第 $$$i$$$ 行中第 $$$j$$$ 个位置的整数 $$$a_{i,j}$$$ 表示第 $$$i$$$ 东边街道和第 $$$j$$$ 南向交叉处的摩天大楼的高度。
输出
打印 $$$n$$$ 行,每行包含 $$$m$$$ 个整数。位于第 $$$i$$$ 行内第 $$$j$$$ 个位置的整数 $$$x_{i,j}$$$ 是第 $$$i$$$-th Eastern 街道和 $$$j$$$-th Southern 街道交叉口问题的答案。
示例
输入 #1
2 3 1 2 1 2 1 2
输出 #1
2 2 2 2 2 2
输入 #2
2 2 1 2 3 4
输出 #2
2 3 3 2
注意
在第一个示例中,不可能减少任何交叉点处问题的最大使用高度,因此我们不必更改任何高度。
在第二个示例中,答案如下:
- 对于第一行和第一列的交集
- 对于第一行和第二列的交集
- 对于第二行和第一列的交点
- 对于第二行和第二列的交点