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;
using nagai = long long;
#define sz(x) int((x).size())

const int H=1010;
bool matr[H][H];
int d[H][H];
int h,w;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>h>>w;
	vector<pair<int,int>>q;
	for(int i=0;i<h;++i)
		for(int j=0;j<w;++j)d[i][j]=-1;
	for(int i=0;i<h;++i){
		string s;
		cin>>s;
		for(int j=0;j<w;++j){
			matr[i][j]=s[j]=='#';
			if(matr[i][j])
				q.emplace_back(i,j),d[i][j]=0;
		}
	}
	vector<int>dx={1,0,-1,0},dy={0,1,0,-1};
	int mx=0;
	for(int i=0;i<q.size();++i){
		int x=q[i].first;
		int y=q[i].second;
		mx=max(mx,d[x][y]);
		for(int k=0;k<4;++k){
			int x1=x+dx[k];
			int y1=y+dy[k];
			if(x1>=0&&y1>=0&&x1<h&&y1<w&&d[x1][y1]==-1)
				d[x1][y1]=d[x][y]+1,q.emplace_back(x1,y1);
		}
	}
	cout<<mx<<'\n';
	return 0;
}