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.io.*;

import static java.lang.System.in;

public class Main {
    static int[] dat;
    static int n=1;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        //PrintWriter out = new PrintWriter(System.out);
        //BufferedReader reader = new BufferedReader(new InputStreamReader(in));
        //String[] buf = reader.readLine().split(" ");
        int H = sc.nextInt(), W = sc.nextInt();
        int[][] grid = new int[H][W];
        List<int[]> que = new LinkedList<>(), next = new LinkedList<>();
        for(int i=0;i<H;i++){
            char[] s = sc.next().toCharArray();
            for(int j=0;j<W;j++){
                if(s[j]=='#') {
                    grid[i][j]=1;
                    que.add(new int[]{i,j});
                }
            }
        }
        if(que.size()==H*W){
            System.out.println(0);
            return;
        }
        int step = 0;
        int[] dr = new int[]{1,0,-1,0}, dc=new int[]{0,1,0,-1};
        while(que.size()>0){
            for(int[] w:que){
                for(int i=0;i<4;i++){
                    int r=w[0]+dr[i], c=w[1]+dc[i];
                    if(r>=0&&r<H&&c>=0&&c<W&&grid[r][c]==0){
                        next.add(new int[]{r,c});
                        grid[r][c]=1;
                    }
                }
            }
            step++;
            que=next;
            next = new LinkedList<>();
        }
        System.out.println(step-1);
    }
}