配点 : $300$ 点

問題文

縦 $H$ マス横 $W$ マスのグリッドがあります。グリッドの上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ と呼びます。 グリッドの各マスには # と . のいずれかの文字が書かれています。$(i, j)$ に書かれている文字を $C[i][j]$ とします。また、整数 $i, j$ が $1 \leq i \leq H$ と $1 \leq j \leq W$ の少なくとも一方を満たさない場合、 $C[i][j]$ を . と定義します。

正整数 $a, b, n$ が以下の条件を全て満たす時、$(a,b)$ および $(a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d)$ $(1 \leq d \leq n)$ の $4n + 1$ マスを (a,b) を中心とするサイズ n のバツ印 と呼びます。

• $C[a][b]$ は # である。
• $1 \leq d \leq n$ を満たす整数 $d$ について、 $C[a+d][b+d],C[a+d][b-d],C[a-d][b+d],C[a-d][b-d]$ はいずれも # である。
• $C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1],C[a-n-1][b-n-1]$ のうち少なくとも 1 つは . である。

例えば次の図で示された例では、$(2, 2)$ を中心とするサイズ $1$ のバツ印と $(3, 7)$ を中心とするサイズ $2$ のバツ印がグリッド上にあります。

グリッドにはいくつかのバツ印があります。バツ印を構成するマス以外に # は書かれていません。 また、異なるバツ印を構成するマス同士は頂点を共有しません。以下の 2 つのグリッドは異なるバツ印を構成するマス同士が頂点を共有している例で、このようなグリッドの状態は入力として与えられません。 例えば左のグリッドでは $(3, 3)$ と $(4, 4)$ が頂点を共有しているのが条件に反しています。

$N = \min(H, W)$ とします。また、サイズ $n$ のバツ印の個数を $S_n$ とします。$S_1, S_2, \dots, S_N$ を計算してください。

制約

• $3 \leq H, W \leq 100$
• $C[i][j]$ は # または .
• 異なるバツ印を構成するマス同士は頂点を共有しない
• $H, W$ は整数

入力

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

$H$ $W$

$C[1][1]C[1][2]\dots C[1][W]$

$C[2][1]C[2][2]\dots C[2][W]$

$\vdots$

$C[H][1]C[H][2]\dots C[H][W]$

出力

$S_1, S_2, \dots, S_N$ を空白区切りで出力せよ。

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

1 1 0 0 0

問題文に書かれた説明の通り、$(2, 2)$ を中心とするサイズ $1$ のバツ印と $(3, 7)$ を中心とするサイズ $2$ のバツ印が書かれています。

3 3
...
...
...

0 0 0

バツ印が 1 個も書かれていない場合もあります。

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

3 0 0

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0