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 <iostream>
#include <queue>
#define pii pair<int,int>
#define ppi pair<pii,int>
#define fst first
#define snd second
const int dr[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
using namespace std;
queue<ppi> q;int n,m,mx=0;string mp[1001]={};bool bt[1001][1001]={};
bool isv(pii dt) {return dt.fst>=0&&dt.fst<n&&dt.snd>=0&&dt.snd<m;}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for (int i=0;i<n;i++) 
	{
		cin>>mp[i];
		for (int j=0;j<m;j++)
		{
			if (mp[i][j]=='#') {q.push({{i,j},0});}
		}
	}
	while (!q.empty())
	{
		ppi dt = q.front();q.pop();
		if (!bt[dt.fst.fst][dt.fst.snd])
		{
			bt[dt.fst.fst][dt.fst.snd] = 1;
			mx = dt.snd;
			for (int i=0;i<4;i++)
			{
				if (isv({dt.fst.fst+dr[i][0],dt.fst.snd+dr[i][1]})) {q.push({{dt.fst.fst+dr[i][0],dt.fst.snd+dr[i][1]},dt.snd+1});}
			}
		}
	}
	cout<<mx<<"\n";
	return 0;
}