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 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		char[][] A = new char[H+2][W+2];
		for(int i = 1; i <= H; i++) {
			String S = sc.next();
			for(int j = 1; j <= W; j++)
				A[i][j] = S.charAt(j-1);
		}
		int ans = 0;
		Queue<Integer> q = new ArrayDeque<>();
		int[][] used = new int[H+2][W+2];
		for(int j = 0; j <= W+1; j++) {
			used[0][j] = 1;
			used[H+1][j] = 1;
		}for(int i = 0; i <= H+1; i++) {
			used[i][0] = 1;
			used[i][W+1] = 1;
		}
		for(int i = 1; i <= H; i++)
			for(int j = 1; j <= W; j++)
				if(A[i][j] == '#') {
					q.offer(i*(W+2)+j);
					used[i][j] = 1;
				}
		while(q.size() > 0) {
			int x = q.poll();
			int i = x / (W+2), j = x % (W+2);
			if(used[i-1][j] == 0) {
				used[i-1][j] = used[i][j]+1;
				q.offer((i-1)*(W+2)+j);
			}
			if(used[i+1][j] == 0) {
				used[i+1][j] = used[i][j]+1;
				q.offer((i+1)*(W+2)+j);
			}
			if(used[i][j-1] == 0) {
				used[i][j-1] = used[i][j]+1;
				q.offer(i*(W+2)+j-1);
			}
			if(used[i][j+1] == 0) {
				used[i][j+1] = used[i][j]+1;
				q.offer(i*(W+2)+j+1);
			}	
			ans = used[i][j] - 1;
		}
		System.out.println(ans);
	}

}