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<bits/stdc++.h>
using namespace std;
int n,m;
bool b[1010][1010];
char c[1010];
struct bfs{
	int x,y,bs;
}q[1000010];
int h=0,t=0;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		scanf("%s",c+1);
		for(int j=1;j<=m;j++){
			b[i][j]=(c[j]=='#');
			if(b[i][j]==1)q[++t]={i,j,0};
		}

	}
	while(h<t){
		bfs now=q[++h];int cs=now.bs+1;
		if(now.x>1&&b[now.x-1][now.y]==0)
		q[++t]={now.x-1,now.y,cs},b[now.x-1][now.y]=1;
		if(now.x<n&&b[now.x+1][now.y]==0)
		q[++t]={now.x+1,now.y,cs},b[now.x+1][now.y]=1;
		
		if(now.y>1&&b[now.x][now.y-1]==0)
		q[++t]={now.x,now.y-1,cs},b[now.x][now.y-1]=1;
		if(now.y<m&&b[now.x][now.y+1]==0)
		q[++t]={now.x,now.y+1,cs},b[now.x][now.y+1]=1;
	}
	cout<<q[t].bs;
	return 0;
}