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.*;
import java.awt.Point;
public class Main{
	public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int dx[] = {0, 1, 0, -1};
        int dy[] = {1, 0, -1, 0};

        int h = sc.nextInt();
        int w = sc.nextInt();
        char map[][] = new char[h][w];
        int a[][] = new int[h][w];
        int INF = Integer.MAX_VALUE;
        for(int[] n: a){
            Arrays.fill(n,INF);
        }
        Queue<Point> queue = new ArrayDeque<>();
        for(int i=0; i<h; i++){
            map[i] = sc.next().toCharArray();
            for(int j=0; j<w; j++){
                if(map[i][j]=='#'){
                    queue.add(new Point(i,j));
                    a[i][j] = 0;
                }
            } 
        }
        int memo = 0;
        while(!queue.isEmpty()){
            Point p = queue.poll();
            for(int k=0; k<4; k++){
                int X = p.x + dx[k];
                int Y = p.y + dy[k];
                if(X>=0 && X<h && Y>=0 && Y<w && a[X][Y]==INF){
                    a[X][Y] = a[p.x][p.y] + 1;
                    queue.add(new Point(X,Y));
                    memo = a[X][Y];
                }
            }
        }
        System.out.println(memo);
    }
}