3295 - [NOI Online #3 入门组] 观星
描述

Jimmy 和 Symbol 约好一起看星星,浩瀚的星空可视为一个长为 N、宽为 M 的矩阵,矩阵中共有 N\times M 个位置,一个位置可以用坐标 (i,j)1\le i\le N1\le j\le M)来表示。每个位置上可能是空的,也可能有一个星星。

对于一个位置 (i,j),与其相邻的位置有左边、左上、上面、右上、右边、右下、下面、左下 8 个位置。相邻位置上的星星被视为同一个星座,这种关系有传递性,例如若 (1,1),(1,2),(1,3) 三个

位置上都有星星,那么这三个星星视为同一个星座。包含的星星数量相同的星座被视为一个星系(一个星系中的星座不一定相邻),星系的大小为星系中包含的所有星星数量。

由于 Symbol 太喜欢星系了,他就想考一考 Jimmy,让 Jimmy 求出星空中有多少个星系,他还想知道,最大的星系有多大。


输入

第一行两个整数 N,M 表示矩阵的长宽。

接下来 N 行每行 M 个字符,每个字符只可能是`.`或`*`。这 N 行中第 i 行的第 j 个字符是`*`表示位置 (i,j) 上有一个星星,否则表示它是空的。


输出

仅一行两个整数,用空格分隔开,分别表示星系的数量与最大星系的大小。

样例

输入

5 7
*......
..**..*
.*...*.
...*...
....*..

输出

3 4

输入

10 10
**..**.**.
***....*..
*...**.**.
...*..*...
..........
**...**.*.
..*.*....*
..........
***..*.*..
.***..*...

输出

4 12
提示

对于 20\% 的数据,N,M\le 20,最大星系大小不超过 200。

对于 50\% 的数据,N,M\le 400

对于 70\% 的数据,N,M\le 1100

对于 100\% 的数据,2\le N,M\le 1500,最大星系大小不超过 100000。


标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 16
通过次数 5