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.*;
public class Main {
	int h;
	int w;
	int[][] hw;
	int q = 0;
	int qnum = 0;
	ArrayList<Integer> queue = new ArrayList<Integer>();
	int max = 0;

	Main(){
		Scanner sc = new Scanner(System.in);

		// 整数の入力
		h = sc.nextInt();
		w = sc.nextInt();
		hw = new int[h][w];

		// 文字列の入力
		for(int y=0;y<h;y++){
			String s = sc.next();
			String[] S = s.split("");
			for(int x=0;x<w;x++){
				if(S[x].equals("#")){
					hw[y][x]=0;
					queue.add(y);
					queue.add(x);
					qnum+=2;
				} else {
					hw[y][x]=2000;
				}
			}
		}

		//走査
		while(q<qnum){
			change(queue.get(q),queue.get(q+1));
			q+=2;
		}

		// 出力
		System.out.println(max);
	}

	public void change(int y,int x){
		if(y+1<h&&hw[y+1][x]>hw[y][x]+1){
			hw[y+1][x]=hw[y][x]+1;
			queue.add(y+1);
			queue.add(x);
			qnum+=2;
			if(max<hw[y][x]+1)max = hw[y][x]+1;
		}
		if(y>0&&hw[y-1][x]>hw[y][x]+1){
			hw[y-1][x]=hw[y][x]+1;
			queue.add(y-1);
			queue.add(x);
			qnum+=2;
			if(max<hw[y][x]+1)max = hw[y][x]+1;
		}
		if(x>0&&hw[y][x-1]>hw[y][x]+1){
			hw[y][x-1]=hw[y][x]+1;
			queue.add(y);
			queue.add(x-1);
			qnum+=2;
			if(max<hw[y][x]+1)max = hw[y][x]+1;
		}
		if(x+1<w&&hw[y][x+1]>hw[y][x]+1){
			hw[y][x+1]=hw[y][x]+1;
			queue.add(y);
			queue.add(x+1);
			qnum+=2;
			if(max<hw[y][x]+1)max = hw[y][x]+1;
		}
	}

	public static void main(String[] args){
		new Main();
	}
}