题目背景

“几处浓淡生涟漪，一纸素笔任挥洒。”

他不经意间在纸上的几处落下了滴滴水墨。墨迹未干，正像水波涟漪一般，顺着宣纸的纹理向四周缓缓晕染开来。

题目描述

我们可以将宣纸看作一个 $N \times M$ 的二维网格。在 $t = 0$ 时刻，网格中有若干个格子被滴上了水墨。每一秒钟，水墨都会向着上、下、左、右、左上、左下、右上、右下八个相邻的格子蔓延。现给出宣纸的初始状态，请你推演并计算出：宣纸多久会被完全染黑？

输入

第一行包含两个正整数 $N$ 和 $M$，表示宣纸的长和宽。 接下来的 $N$ 行，每行包含一个长度为 $M$ 的字符串，表示宣纸的初始状态： 字符 * 表示该位置在 $t = 0$ 时刻被滴上了水墨（可能有多个）。 字符 . 表示该位置是空白的宣纸。

输出

输出一行一个整数表示染黑宣纸所用的时间。

样例说明

4 5
.....
..*..
.....
*....

2

限制条件

• 对于 $30\%$ 的数据，$1 \le N, M \le 50$。
• 对于 $60\%$ 的数据，$1 \le N, M \le 500$。
• 对于 $100\%$ 的数据，$1 \le N, M \le 2000$。
• 保证初始网格中至少有一个 * 字符。
• 时间限制：1s
• 空间限制：256MiB