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 final int INF = (int)1e9+7;
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int h = sc.nextInt();
        int w = sc.nextInt();
        
        int[][] dist = new int[h][w];
        ArrayDeque<Integer> q = new ArrayDeque<>();
        
        for(int i=0; i<h; i++){
            char[] s = sc.next().toCharArray();
            for(int j=0; j<w; j++){
                if(s[j]=='#'){
                    dist[i][j] = 0;
                    q.addLast(i*w+j);
                }else{
                    dist[i][j] = INF;
                }
            }
        }
        
        int ans = 0;
        while(q.size()!=0){
            int now = q.removeFirst();
            int y = now/w;
            int x = now%w;
            ans = Math.max(ans, dist[y][x]);
            if(y+1<h && dist[y+1][x]>dist[y][x]+1){
                dist[y+1][x] = dist[y][x]+1;
                q.addLast((y+1)*w+x);
            }
            if(0<=y-1 && dist[y-1][x]>dist[y][x]+1){
                dist[y-1][x] = dist[y][x]+1;
                q.addLast((y-1)*w+x);
            }
            if(x+1<w && dist[y][x+1]>dist[y][x]+1){
                dist[y][x+1] = dist[y][x]+1;
                q.addLast(y*w+x+1);
            }
            if(0<=x-1 && dist[y][x-1]>dist[y][x]+1){
                dist[y][x-1] = dist[y][x]+1;
                q.addLast(y*w+x-1);
            }
        }
        
        System.out.println(ans);
    }
}