Problem: You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black. HW characters from A_{11} to A_{HW} represent the colors of the squares. A_{ij} is `#` if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is `.` if that square is white.

We will repeatedly perform the following operation until all the squares are black:

* Every white square that shares a side with a black square, becomes black.



Find the number of operations that will be performed. The initial grid has at least one black square.

Constraints

* 1 \leq H,W \leq 1000
* A_{ij} is `#` or `.`.
* The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:


H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}


Output

Print the number of operations that will be performed.

Examples

Input

3 3
...
.#.
...


Output

2


Input

6 6
..#..#
......
..#..
......
.#....
....#.


Output

3

Solution (in CPP):

Solution:
#include<cstdio>
#include<utility>
#include<iostream>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=1005,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
inline char get_ch(void)
{
	char ch; while (ch=getchar(),ch!='#'&&ch!='.'); return ch;
}
int n,m,stp[N][N],ans; pi q[N*N];
int main()
{
	RI i,j,H=0,T=0; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
	for (j=1;j<=m;++j) if (get_ch()=='#') q[++T]=mp(i,j); else stp[i][j]=1e9;
	while (H<T)
	{
		int nx=q[++H].fi,ny=q[H].se; for (i=0;i<4;++i)
		{
			int tx=nx+dx[i],ty=ny+dy[i];
			if (tx>=1&&tx<=n&&ty>=1&&ty<=m&&stp[tx][ty]>stp[nx][ny]+1)
			stp[tx][ty]=stp[nx][ny]+1,q[++T]=mp(tx,ty);
		}
	}
	for (i=1;i<=n;++i) for (j=1;j<=m;++j) ans=max(ans,stp[i][j]);
	return printf("%d",ans),0;
}