29023번 - 井の中の蛙 다국어

문제

h × w の等間隔の格子点があり,上から r 番目,左から c 番目の位置を (r, c) とする (1 ≤ r ≤ h, 1 ≤ c ≤ w).各格子点上に1匹ずつ蛙がいる.各々の蛙は強さが数値化されており,位置 (r, c) にいる蛙の強さは f_{r, c} である.だが,彼らはみな,自分が世界で一番強いと思っている井の中の蛙である.彼らは自分より強い蛙がいない範囲を直感的に把握しており,その範囲内のみで活動することによりそのアイデンティティを保っている.

位置 (r₁, c₁) と位置 (r₂, c₂) との距離を |r₁ - r₂| + |c₁ - c₂| と定義する.このとき,位置 (r, c) にいる蛙は,距離 d 以内に自分より厳密に強い蛙がいないければ,この範囲で活動できる.すなわち,|r - i| + |c - j| ≤ d を満たすすべての 1 ≤ i ≤ h, 1 ≤ j ≤ w について,f_{i, j} ≤ f_{r, c} であれば,位置 (r, c) にいる蛙は距離 d の範囲で活動できる.

格子上の蛙たちがどれだけ井の中の蛙なのかの度合い,通称「井度」を把握するため,あなたにプログラムの作成依頼が飛び込んだ.各距離 d = 1, 2, ..., h + w - 2 について,距離 d の範囲で活動可能な蛙の数を求めるプログラムを作成し,あなたがプログラミング界の井の中の蛙ではないことを証明しよう.

입력

入力は複数のデータセットからなる. 各データセットは次の形式で表される.

h w

f_1,1 f_1,2 ... f_1,w

f_2,1 f_2,2 ... f_2,w

...

f_h,1 f_h,2 ... f_h,w

入力の 1 行目は格子の大きさを表す 2 つの整数 h と w からなり, 1 ≤ h ≤ 1,000,1 ≤ w ≤ 1,000,h + w ≥ 3 を満たす.続く h 行は各行 w 個の整数からなり,各蛙の強さの情報である.r 行目の c 番目の整数は位置 (r, c) の蛙の強さ f_{r, c} を表す.各 f_{r, c} はいずれも 1 以上 10⁹ 以下である.

入力の終わりは 2 つのゼロからなる行で表される. 入力に含まれるデータセットは 50 個以内である.

출력

各データセットに対して,h + w - 2 個の整数を空白区切りで 1 行に出力せよ.ここで,行内の i 番目の整数は,距離 i 以内に自分より強い蛙が存在しないような蛙の数である.

제한

힌트