题目描述

我们有一个 $H$ 行 $W$ 列的网格。记从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子为 $(i, j)$。

网格中的每个格子上写有字符 # 或 .。记 $C[i][j]$ 为写在 $(i, j)$ 上的字符。对于违反 $1 \le i \le H$ 或 $1 \le j \le W$ 中至少一个条件的整数 $i$ 和 $j$，我们规定 $C[i][j]$ 为 .。

一个以 $(a, b)$ 为中心、大小为 $n$（$n \ge 1$）的“十字”由 $(4n+1)$ 个格子组成，包含 $(a, b)$ 以及 $(a+d, b+d), (a+d, b-d), (a-d, b+d), (a-d, b-d)$（$1 \le d \le n$）。这 $(4n+1)$ 个格子能被称为十字，当且仅当满足以下所有条件：

• $C[a][b]$ 是 #。
• 对于所有满足 $1 \le d \le 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]$ 中至少有一个是 .。

例如，下图中的网格有一个以 $(2, 2)$ 为中心、大小为 $1$ 的十字，以及另一个以 $(3, 7)$ 为中心、大小为 $2$ 的十字。

网格中包含若干个十字。除了组成十字的格子外，没有任何其他格子是 #。

此外，属于两个不同十字的任意两个格子不会共用一个角（即不会对角相邻）。下图中的两个网格展示了“属于不同十字的两个格子共用一个角”的例子；此类网格不会作为输入给出。例如，左侧的网格是不合法的，因为 $(3, 3)$ 和 $(4, 4)$ 共用了一个角。

设 $N = \min(H, W)$，并令 $S_n$ 为大小为 $n$ 的十字的数量。请计算并输出 $S_1, S_2, \dots, S_N$。

输入格式

第一行包含两个正整数 $H$ 和 $W$ —— 分别表示网格的行数和列数。

接下来 $H$ 行，每行包含一个长度为 $W$ 的字符串。其中第 $i$ 行的第 $j$ 个字符表示 $C[i][j]$。

输出格式

输出一行，包含 $N$ 个整数 $S_1, S_2, \dots, S_N$，相邻两个整数之间用一个空格隔开。

样例输入 1

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

样例输出 1

1 1 0 0 0

样例输入 2

3 3
...
...
...

样例输出 2

0 0 0

样例输入 3

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

样例输出 3

3 0 0

样例输入 4

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

样例输出 4

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

说明

样例解释

• 在第一个样例中，如题目描述所述，存在一个以 $(2, 2)$ 为中心、大小为 $1$ 的十字，以及一个以 $(3, 7)$ 为中心、大小为 $2$ 的十字。
• 在第二个样例中，网格中可能不存在任何十字。

数据范围

• 对于所有测试点，保证 $3 \le H, W \le 100$。
• 保证 $C[i][j]$ 均为 # 或 .。
• 保证属于两个不同十字的任意两个格子不会共用一个角。
• 保证所有的 $H$ 和 $W$ 均为整数。