우물 안 개구리

격자점이 $h \times w$개 있고, 위에서 $r$번째, 왼쪽에서 $c$번째 위치를 $(r, c)$라고 한다 ($1 \le r \le h$, $1 \le c \le w$). 각 격자점에는 개구리가 한 마리씩 있다. 개구리마다 강도를 나타내는 값이 정해져 있으며, 위치 $(r, c)$의 개구리 강도는 $f_{r,c}$이다.

그런데 개구리들은 모두 자신이 세상에서 가장 강하다고 믿는 우물 안 개구리다. 각 개구리는 자신보다 강한 개구리가 없는 범위를 직감적으로 알고 있으며, 그 범위 안에서만 활동함으로써 정체성을 지킨다.

두 위치 $(r_1, c_1)$과 $(r_2, c_2)$ 사이의 거리는 $|r_1 - r_2| + |c_1 - c_2|$로 정의한다. 위치 $(r, c)$의 개구리는 거리 $d$ 이내에 자신보다 엄격하게 강한 개구리가 없으면 그 범위에서 활동할 수 있다. 즉, $|r - i| + |c - j| \le d$를 만족하는 모든 $1 \le i \le h$, $1 \le j \le w$에 대해 $f_{i,j} \le f_{r,c}$이면, 위치 $(r, c)$의 개구리는 거리 $d$ 범위에서 활동할 수 있다.

격자 위 개구리들이 얼마나 우물 안 개구리인지 나타내는 정도, 일명 井度(정도)를 파악하기 위해 프로그램을 작성하자. 각 거리 $d = 1, 2, \ldots, h + w - 2$에 대해 거리 $d$ 범위에서 활동할 수 있는 개구리의 수를 구하는 프로그램을 작성하여, 프로그래밍 세계의 우물 안 개구리가 아님을 증명하자.

입력은 여러 데이터셋으로 이루어진다. 각 데이터셋은 다음 형식으로 주어진다.

h w
f1,1 f1,2 ... f1,w
f2,1 f2,2 ... f2,w
...
fh,1 fh,2 ... fh,w

첫 줄에는 격자의 크기를 나타내는 정수 $h$와 $w$가 주어지며, $1 \le h \le 1{,}000$, $1 \le w \le 1{,}000$, $h + w \ge 3$을 만족한다. 이어서 $h$줄에 걸쳐 각 줄마다 $w$개의 정수가 주어지며, 이는 각 개구리의 강도다. $r$번째 줄의 $c$번째 정수가 위치 $(r, c)$의 개구리 강도 $f_{r,c}$이며, $1 \le f_{r,c} \le 10^9$이다. 입력의 끝은 두 개의 0으로 이루어진 줄이다. 데이터셋은 50개 이하다.

각 데이터셋에 대해 $h + w - 2$개의 정수를 공백으로 구분하여 한 줄에 출력한다. $i$번째 정수는 거리 $i$ 이내에 자신보다 강한 개구리가 존재하지 않는 개구리의 수다.