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();
        boolean po[][]=new boolean[h][w];
        ArrayList<int[]>oder=new ArrayList<>();
        for(int i=0;i<h;i++){
            String s[]=sc.next().split("",0);
            for(int j=0;j<w;j++){
                po[i][j]=s[j].equals("#");
                if(s[j].equals("#"))oder.add(new int[]{j,i});
            }
        }
        
        boolean b=false;
        int count=0,count2=0;
        oder.add(new int[]{-1,-1});
        while(true){
            int[]o=oder.get(count2);
            count2++;
            if(o[0]==-1&&o[1]==-1){
                if(!b)break;
                b=false;
                count++;
                oder.add(new int[]{-1,-1});
            }   
            else{
                if(o[0]!=w-1){
                    if(!po[o[1]][o[0]+1]){
                        oder.add(new int[]{o[0]+1,o[1]});
                        po[o[1]][o[0]+1]=true;
                        b=true;
                    }
                }
                if(o[0]!=0){
                    if(!po[o[1]][o[0]-1]){
                        oder.add(new int[]{o[0]-1,o[1]});
                        po[o[1]][o[0]-1]=true;
                        b=true;
                    }
                }
                if(o[1]!=h-1){
                    if(!po[o[1]+1][o[0]]){
                        oder.add(new int[]{o[0],o[1]+1});
                        po[o[1]+1][o[0]]=true;
                        b=true;
                    }
                }
                if(o[1]!=0){
                    if(!po[o[1]-1][o[0]]){
                        oder.add(new int[]{o[0],o[1]-1});
                        po[o[1]-1][o[0]]=true;
                        b=true;
                    }
                }
                
            }
        }
        System.out.println(count);
    }
}