Frogs in a Well

There is a grid of evenly spaced lattice points with $h \times w$ points. The point in row $r$ from the top and column $c$ from the left is denoted $(r, c)$ ($1 \le r \le h$, $1 \le c \le w$). Each lattice point holds one frog. Each frog has a strength value, and the frog at $(r, c)$ has strength $f_{r,c}$.

However, every frog is a frog in a well: it believes it is the strongest in the world. Each frog intuitively knows the area where no stronger frog exists, and it keeps its identity by staying active only within that area.

The distance between $(r_1, c_1)$ and $(r_2, c_2)$ is $|r_1 - r_2| + |c_1 - c_2|$. A frog at $(r, c)$ can be active within distance $d$ if no frog within distance $d$ is strictly stronger than it. That is, if $f_{i,j} \le f_{r,c}$ for every $1 \le i \le h$ and $1 \le j \le w$ with $|r - i| + |c - j| \le d$, then the frog at $(r, c)$ can be active within distance $d$.

To measure how much of a frog in a well each frog is, called the well degree, you are asked to write a program. For each distance $d = 1, 2, \ldots, h + w - 2$, the program counts the frogs that can be active within distance $d$. Write it and show that you are not a frog in the programming world.

The input consists of multiple datasets. Each dataset has the following format.

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

The first line contains two integers $h$ and $w$ with $1 \le h \le 1{,}000$, $1 \le w \le 1{,}000$, and $h + w \ge 3$. The next $h$ lines each contain $w$ integers, the strengths of the frogs. The $c$-th integer on the $r$-th line is $f_{r,c}$, with $1 \le f_{r,c} \le 10^9$. The input ends with a line containing two zeros. There are at most 50 datasets.

For each dataset, print $h + w - 2$ integers separated by spaces on one line. The $i$-th integer is the number of frogs for which no frog within distance $i$ is stronger than them.