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 static java.lang.System.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int[][] A = new int[1000][1000];

    public static void main(String[] args) {
        int H = ni();
        int W = ni();

        for (int h = 0; h < H; h++) {
            for (int w = 0; w < W; w++) {
                A[h][w] = -1;
            }
        }

        for (int h = 0; h < H; h++) {
            String astr = sc.next();
            for (int w = 0; w < W; w++) {
                if (astr.charAt(w) == '#') {
                    A[h][w] = 0;
                }
            }
        }

        // 2回累積和
        accum(H, W);
        accum(H, W);

        int ans = 0;
        for (int h = 0; h < H; h++) {
            for (int w = 0; w < W; w++) {
                ans = Math.max(ans, A[h][w]);
            }
        }

        out.println(ans);
    }

    static void accum(int H, int W) {
        // 右
        for (int h = 0; h < H; h++) {
            for (int w = 0; w < W; w++) {
                if (A[h][w] != -1) {
                    w++;
                    while (w < W && (A[h][w] == -1 || A[h][w - 1] < A[h][w])) {
                        A[h][w] = A[h][w - 1] + 1;
                        w++;
                    }
                    w--;
                }
            }
        }

        // 左
        for (int h = 0; h < H; h++) {
            for (int w = W - 1; w >= 0; w--) {
                if (A[h][w] != -1) {
                    w--;
                    while (w >= 0 && (A[h][w] == -1 || A[h][w] > A[h][w + 1])) {
                        A[h][w] = A[h][w + 1] + 1;
                        w--;
                    }
                    w++;
                }
            }
        }

        // 下
        for (int w = 0; w < W; w++) {
            for (int h = 0; h < H; h++) {
                if (A[h][w] != -1) {
                    h++;
                    while (h < H && (A[h][w] == -1 || A[h - 1][w] < A[h][w])) {
                        A[h][w] = A[h - 1][w] + 1;
                        h++;
                    }
                    h--;
                }
            }
        }

        // 上
        for (int w = 0; w < W; w++) {
            for (int h = H - 1; h >= 0; h--) {
                if (A[h][w] != -1) {
                    h--;
                    while (h >= 0 && (A[h][w] == -1 || A[h][w] > A[h + 1][w])) {
                        A[h][w] = A[h + 1][w] + 1;
                        h--;
                    }
                    h++;
                }
            }
        }
    }

    static int ni() {
        return sc.nextInt();
    }

    static long nl() {
        return sc.nextLong();
    }

    static String ns() {
        return sc.next();
    }

    static int[] niarr(int N) {
        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = sc.nextInt();
        }
        return a;
    }

    static long[] nlarr(int N) {
        long[] a = new long[N];
        for (int i = 0; i < N; i++) {
            a[i] = sc.nextLong();
        }
        return a;
    }
}