条坊制都市

アイヅ京は、その領域が$H \times W$個の区画からなる碁盤目状に区画された条坊制都市である。上から$i$行目、左から$j$列目の区画には番号$(i,j)$がつけられており、各区画$(i,j)$には高さ$A_{i,j}$の建物が建っている。

アイヅ京の帝(みかど)であるあなたは、都市改革の一環として領域の１行分のどこかと１列分のどこかの建物をすべて取り壊して大通りを作ろうとしている。そこで、住民を説得するために以下の要領で京の景観の良さを定義し、それらを基準に大通りの場所を決めることにした。

• 京の全領域$T$から$r$行目と$c$列目を取り除き、残った領域を$T’$とする。
• $T’$内のどの建物の高さとも異なる非負整数のうち最小の値を、$T’$の景観の良さとする。

京の領域の大きさと建物の高さが与えられる。大通りを作る場所の候補それぞれにおける景観の良さを求めるプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$H$ $W$
$A_{1,1}$ $A_{1,2}$ ...  $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ ...  $A_{2,W}$
:
$A_{H,1}$ $A_{H,2}$ ...  $A_{H,W}$

1行目に、領域の縦方向の区画の数$H$ ($2 \leq H \leq 1,500$)と横方向の区画の数$W$ ($2 \leq W \leq 1,500$)が与えられる。続く$H$行に、$i$行目に並ぶ区画に建てられた建物の高さ$A_{i,j}$ ($0 \leq A_{i,j} \leq H \times W-1$)が与えられる。

出力

領域の$r$行目と$c$列目を取り除いたときの景観の良さを$P_{r,c}$としたとき、大通りを作る場所の候補それぞれにおける景観の良さを、以下の形式で出力する。

$P_{1,1}$ $P_{1,2}$ ...  $P_{1,W}$
$P_{2,1}$ $P_{2,2}$ ...  $P_{2,W}$
:
$P_{H,1}$ $P_{H,2}$ ...  $P_{H,W}$

入出力例

入力例１

2 2
0 1
1 2

出力例１

0 0
0 1

入力例２

3 3
0 1 2
1 0 2
2 4 2

出力例２

1 0 3
0 1 3
3 3 2

Note

Algorithm

 

---