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;


const int MAXN = 100001;
typedef long long ll;
#define f first
#define s second
const ll mod = 1e9+7;


int main(){
	int N,M;
	scanf("%d %d",&N,&M);
	char c;
	int chk[N][M], moves[4][2] = {{0,-1},{0,1},{1,0},{-1,0}};
	memset(chk,0,sizeof chk);
	queue<pair<int,int>> q;
	for (int i=0;i<N;i++){
		for (int j=0;j<M;j++){
			scanf(" %c",&c);
			if (c=='#'){
				chk[i][j] = 1;
				q.push({i,j});
			}
		}
	}
	pair<int,int> cur;
	int ans = 0, y, x;
	while (!q.empty()){
		cur = q.front();
		q.pop();
		for (int i=0;i<4;i++){
			y = cur.f+moves[i][0];
			x = cur.s+moves[i][1];
			if (x<0||y<0||y>=N||x>=M) continue;
			if (chk[y][x]) continue;
			chk[y][x] = chk[cur.f][cur.s]+1;
			q.push({y,x});
			ans = max(ans,chk[y][x]-1);
		}
	}
	printf("%d\n",ans);
}