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.awt.*;
import java.util.*;

public class Main{
	static final int dx[]= {0,-1,0,1};
	static final int dy[]= {-1,0,1,0};

	public static void main(String[] $){
		Scanner s=new Scanner(System.in);
		int h=s.nextInt();
		int w=s.nextInt();

		boolean f[][]=new boolean[h][w];

		ArrayDeque<Point> q=new ArrayDeque<>();

		for(int i=0;i<h;++i) {
			char[]t=s.next().toCharArray();
			for(int j=0;j<w;++j) {
				if(t[j]=='#') {
					f[i][j]=true;
					q.add(new Point(j,i));
				}
			}
		}

		int i=-1;
		for(;!q.isEmpty();++i) {
			//for(boolean[]g:f)System.err.println(Arrays.toString(g));
			System.err.println();
			for(int size=q.size();size>0;--size) {
				Point poll=q.poll();
				for(int d=0;d<4;++d) {
					int y=poll.y+dy[d];
					int x=poll.x+dx[d];
					if(0<=y&&y<h&&0<=x&&x<w&&!f[y][x]) {
						f[y][x]=true;
						q.add(new Point(x,y));
					}
				}
			}
		}
		System.out.println(i);
	}
}