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 JAVA):

Solution:
import java.io.*;
import java.util.*;






public class Main
{

	static OutputStream outputStream = System.out;
	static PrintWriter out = new PrintWriter(outputStream);	


	static class node
	{
		int x;int y;int s;

		node(int dx,int dy,int ds)
		{
			x=dx;y=dy;s=ds;
		}
	}


	public static void main(String[] Atul)throws IOException
	{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

		
		String[] s_=br.readLine().split(" ");

		int n=Integer.parseInt(s_[0]),m=Integer.parseInt(s_[1]);


		int[][] vis=new int[n][m];

		int[][] a=new int[n][m];


		for(int i=0;i<n;i++)
		{
			String s1=br.readLine();
			for(int j=0;j<m;j++)
			{
				if(s1.charAt(j)=='#') a[i][j]=1;
				else a[i][j]=0;
			}
		}

		Queue<node> q=new LinkedList<node>();


		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(a[i][j]==1)
				{
					q.add(new node(i,j,0));
					vis[i][j]=1;
				}
			}
		}

		int max=0;

		while(q.size()>0)
		{
			node top=q.poll();

			int i=top.x,j=top.y,s=top.s;

			max=Math.max(max,s);

			if((j-1)>=0 && vis[i][j-1]==0 && a[i][j-1]==0)
			{
				vis[i][j-1]=1;
				q.add(new node(i,j-1,s+1));
			}
			if((j+1)<m && vis[i][j+1]==0 && a[i][j+1]==0)
			{
				vis[i][j+1]=1;
				q.add(new node(i,j+1,s+1));
			}
			if((i-1)>=0 && vis[i-1][j]==0 && a[i-1][j]==0)
			{
				vis[i-1][j]=1;
				q.add(new node(i-1,j,s+1));
			}
			if((i+1)<n && vis[i+1][j]==0 && a[i+1][j]==0)
			{
				vis[i+1][j]=1;
				q.add(new node(i+1,j,s+1));
			}
		}
		out.println(max);
		
		out.close();

	}
}