CF1137A.Skyscrapers

Dora loves adventures quite a lot. During some journey she encountered an amazing city, which is formed by $n$ streets along the Eastern direction and $m$ streets across the Southern direction. Naturally, this city has $nm$ intersections. At any intersection of $i$-th Eastern street and $j$-th Southern street there is a monumental skyscraper. Dora instantly became curious and decided to explore the heights of the city buildings.

When Dora passes through the intersection of the $i$-th Eastern and $j$-th Southern street she examines those two streets. After Dora learns the heights of all the skyscrapers on those two streets she wonders: how one should reassign heights to the skyscrapers on those two streets, so that the maximum height would be as small as possible and the result of comparing the heights of any two skyscrapers on one street wouldn't change.

Formally, on every of $nm$ intersections Dora solves an independent problem. She sees $n + m - 1$ skyscrapers and for each of them she knows its real height. Moreover, any two heights can be compared to get a result "greater", "smaller" or "equal". Now Dora wants to select some integer $x$ and assign every skyscraper a height from $1$ to $x$. When assigning heights, Dora wants to preserve the relative order of the skyscrapers in both streets. That is, the result of any comparison of heights of two skyscrapers in the current Eastern street shouldn't change and the result of any comparison of heights of two skyscrapers in current Southern street shouldn't change as well. Note that skyscrapers located on the Southern street are not compared with skyscrapers located on the Eastern street only. However, the skyscraper located at the streets intersection can be compared with both Southern and Eastern skyscrapers. For every intersection Dora wants to independently calculate the minimum possible $x$.

For example, if the intersection and the two streets corresponding to it look as follows:

Then it is optimal to replace the heights of the skyscrapers as follows (note that all comparisons "less", "equal", "greater" inside the Eastern street and inside the Southern street are preserved)

The largest used number is $5$, hence the answer for this intersection would be $5$.

Help Dora to compute the answers for each intersection.

朵拉非常喜欢冒险。在某次旅途中，她遇到了一座令人惊叹的城市，该城市由 $n$ 条东西向街道和 $m$ 条南北向街道构成（注：原文中“across the Southern direction”意为“沿南北方向”，即通常所称的“南北向”街道）。自然地，这座城市共有 $nm$ 个交叉路口。在第 $i$ 条东西向街道与第 $j$ 条南北向街道的交叉路口处，矗立着一座宏伟的摩天大楼。朵拉立刻产生了浓厚兴趣，决定探究整座城市建筑的高度分布。

每当朵拉经过第 $i$ 条东西向街道与第 $j$ 条南北向街道的交叉路口时，她会考察这两条街道。在获知这两条街道上所有摩天大楼的实际高度后，她思考如下问题：应如何重新为这两条街道上的摩天大楼分配高度，使得所有新高度中的最大值尽可能小，同时保持同一条街道上任意两座大楼之间的高度比较结果不变（即“更大”、“更小”或“相等”的关系均需保留）。

形式化地说，在全部 $nm$ 个交叉路口处，朵拉各自独立求解一个子问题。在每个交叉路口，她观察到 $n + m - 1$ 座摩天大楼（即该东西向街道上的全部 $n$ 座，以及该南北向街道上的全部 $m$ 座，但二者在交叉路口处的那座大楼被重复计算一次，故总计 $n+m-1$ 座），且已知每座大楼的真实高度。此外，任意两个高度均可相互比较，得到“更大”、“更小”或“相等”的结果。现在，朵拉希望选定某个整数 $x$，并将每座摩天大楼的高度重新赋值为 $1$ 到 $x$ 之间的某个整数。在赋值过程中，她要求严格保持两条街道各自的相对顺序：即，当前东西向街道上任意两座大楼之间的高度比较结果不得改变；当前南北向街道上任意两座大楼之间的高度比较结果也不得改变。注意：仅位于同一条街道（即同为东西向街道上，或同为南北向街道上）的大楼之间才进行比较；但位于交叉路口处的那座大楼，既属于东西向街道，也属于南北向街道，因此它将分别与该东西向街道上的其他大楼、以及该南北向街道上的其他大楼进行比较。对每个交叉路口，朵拉希望独立计算出满足条件的最小可能的 $x$ 值。

例如，若某交叉路口及其对应的两条街道结构如下所示：

则最优的高度重赋值方案如下（注意：东西向街道内部及南北向街道内部的所有“小于”、“等于”、“大于”关系均被完整保留）：

其中所用到的最大数字为 $5$，因此该交叉路口的答案为 $5$。

请帮助朵拉计算每个交叉路口对应的答案。

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 1000$) — the number of streets going in the Eastern direction and the number of the streets going in Southern direction.

Each of the following $n$ lines contains $m$ integers $a_{i,1}$, $a_{i,2}$, ..., $a_{i,m}$ ($1 \le a_{i,j} \le 10^9$). The integer $a_{i,j}$, located on $j$-th position in the $i$-th line denotes the height of the skyscraper at the intersection of the $i$-th Eastern street and $j$-th Southern direction.

第一行包含两个整数 $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$ 条南北向街道交汇处的摩天大楼的高度。

Print $n$ lines containing $m$ integers each. The integer $x_{i,j}$, located on $j$-th position inside the $i$-th line is an answer for the problem at the intersection of $i$-th Eastern street and $j$-th Southern street.

输出 $n$ 行，每行包含 $m$ 个整数。位于第 $i$ 行第 $j$ 列的整数 $x_{i,j}$，表示第 $i$ 条东向街道与第 $j$ 条南向街道交汇处对应问题的答案。

In the first example, it's not possible to decrease the maximum used height for the problem at any intersection, hence we don't have to change any heights.

In the second example, the answers are as follows:

• For the intersection of the first line and the first column
• For the intersection of the first line and the second column
• For the intersection of the second line and the first column
• For the intersection of the second line and the second column

在第一个例子中，无法降低任意交叉点处问题所使用的最大高度，因此我们无需更改任何高度。

在第二个例子中，答案如下：

• 第一行与第一列的交叉点：
• 第一行与第二列的交叉点：
• 第二行与第一列的交叉点：
• 第二行与第二列的交叉点：