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.util.LinkedList;
import java.util.Scanner;
import java.util.Vector;

public class Main 
{
	static class Tile
	{
		int x;
		int y;
		public Tile(int x0, int y0)
		{
			x=x0;
			y=y0;
		}
	}
	static boolean[][] vis;
	static long[][] scr;
	static int h,w;
	static boolean bound(int x, int y)
	{
		if(x<0 || x>=w)return false;
		if(y<0 || y>=h)return false;
		return true;
	}
	
	public static void main(String[] args) 
	{
		Scanner sc = new Scanner(System.in);
		h = sc.nextInt();
		w = sc.nextInt();
		
		vis = new boolean[w][h];
		scr = new long[w][h];
		
		LinkedList<Tile> q = new LinkedList<>();
		Vector<Tile> qq = new Vector<Tile>();
		long bl = 0;
		
		for(int y = 0; y < h; y++)
		{
			String s = sc.next();
			for(int x = 0; x < w; x++)
			{
				if(s.charAt(x) == '#')
				{
					vis[x][y] = true;
					q.add(new Tile(x,y));
					bl++;
					scr[x][y] = 0;
				}
				else scr[x][y] = 99999999;
			}
		}
		long max = 0;
		while(!q.isEmpty())
		{
			Tile t = q.pop();
			int x = t.x;
			int y = t.y;
			if(bound(x-1,y) && !vis[x-1][y])
			{
				vis[x-1][y]=true;
				scr[x-1][y]=scr[x][y]+1;
				q.add(new Tile(x-1,y));
			}
			if(bound(x+1,y) && !vis[x+1][y])
			{
				vis[x+1][y]=true;
				scr[x+1][y]=scr[x][y]+1;
				q.add(new Tile(x+1,y));
			}
			if(bound(x,y+1) && !vis[x][y+1])
			{
				vis[x][y+1]=true;
				scr[x][y+1]=scr[x][y]+1;
				q.add(new Tile(x,y+1));
			}
			if(bound(x,y-1) && !vis[x][y-1])
			{
				vis[x][y-1]=true;
				scr[x][y-1]=scr[x][y]+1;
				q.add(new Tile(x,y-1));
			}
			max = Math.max(max, scr[x][y]);
		}
		System.out.println(max);
	}

}