BoB002-B: MEX of Matrix

2 secs 1024 MB
kyaneko999's icon kyaneko999

問題

HHWW 列のマス目があります.上から ii 行目,左から jj 列目にあるマスには,整数 Ai,jA_{i,j} が書かれています.
ここで,RiR_i および CjC_j を以下のように定めます.

  • Ri=mex({Ai,1,Ai,2,,Ai,W})(1iH)R_i=\mathrm{mex}(\{A_{i,1},A_{i,2},\dots,A_{i,W}\})\quad(1\le i\le H)
  • Cj=mex({A1,j,A2,j,,AH,j})(1jW)C_j=\mathrm{mex}(\{A_{1,j},A_{2,j},\dots,A_{H,j}\})\quad(1\le j\le W)

計算が苦手なSakkyさんに代わって,すべての RiR_i および CjC_j の値を求めてください.

なお,mex(S)\mathrm{mex}(S) は集合 SS に含まれない最小の非負整数を表します.

制約

  • 入力はすべて整数
  • 1H10001\le H\le 1000
  • 1W10001\le W\le 1000
  • 0Ai,j10000\le A_{i,j}\le 1000

入力

入力は以下の形式で標準入力から与えられる.

H  WH\;W
A1,1  A1,2    A1,WA_{1,1}\;A_{1,2}\;\cdots\;A_{1,W}
A2,1  A2,2    A2,WA_{2,1}\;A_{2,2}\;\cdots\;A_{2,W}
\vdots
AH,1  AH,2    AH,WA_{H,1}\;A_{H,2}\;\cdots\;A_{H,W}

出力

以下の形式で答えを整数で出力しなさい.

R1  R2    RHR_1\;R_2\;\cdots\;R_H
C1  C2    CWC_1\;C_2\;\cdots\;C_W

入出力例

入力例1
2 2
0 1
2 3
出力例1
2 0
1 0

R1=mex({0,1})=2R_1=\mathrm{mex}(\{0,1\})=2R2=mex({2,3})=0R_2=\mathrm{mex}(\{2,3\})=0C1=mex({0,2})=1C_1=\mathrm{mex}(\{0,2\})=1C2=mex({1,3})=0C_2=\mathrm{mex}(\{1,3\})=0 です.

入力例2
1 4
0 1 2 3
出力例2
4
1 0 0 0

HHWW が等しいとは限らないことに注意してください.

提出


Go (1.21)