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) {

        // Read
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        boolean a[][] = new boolean[h][w];

        // Preproc
        Queue<Coord> queue = new ArrayDeque<>();
        String tmp;

        for (int i=0; i<h; i++) {
            tmp = sc.next();
            for (int j=0; j<w; j++) {

                if (tmp.charAt(j) == '#') {
                    a[i][j] = true;
                    queue.add(new Coord(i,j));
                }

            }
        }

        Coord dummy = new Coord(0,0);
        dummy.isDummy = true;
        queue.add(dummy);

        // Counting
        int result = 0;

        while (!queue.isEmpty()) {
            Coord c = queue.remove();
            if (!c.isDummy) {
                for(Coord n : neighbours(c, h-1, w-1)){
                    if(!a[n.x][n.y]) {
                        a[n.x][n.y] = true;
                        queue.add(n);
                    }
                }
            } else {
                if (queue.isEmpty()) {
                    break;
                }
                queue.add(dummy);
                result++;
            }
        }

        System.out.println(result);


    }

    private static List<Coord> neighbours(Coord c, int uBoundX, int uBoundY) {
        List<Coord> r = new ArrayList<>(4);
        if (c.x-1 >= 0) {r.add(new Coord(c.x-1,c.y));}
        if (c.y-1 >= 0) {r.add(new Coord(c.x,c.y-1));}
        if (c.x+1 <= uBoundX) {r.add(new Coord(c.x+1,c.y));}
        if (c.y+1 <= uBoundY) {r.add(new Coord(c.x,c.y+1));}
        return r;
    }


    static class Coord {
        boolean isDummy = false;
        int x; int y;
        Coord(int x, int y){
            this.x = x;
            this.y = y;
        };
    }

}