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.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static final Scanner sc  = new Scanner(System.in);
    static final int MOD = (int) 1E9 + 7;
    static final int INF = Integer.MAX_VALUE;
    static final char BLACK = '#';
    static final char WHITE = '.';
    
    public static void main(String[] args) {
        int H = nint();
        int W = nint();
        char[][] A = nchars2(H, W);
        
        
        int countB = 0;
        int ans = 0;
        Queue<Integer> qh = new ArrayDeque<>();
        Queue<Integer> qw = new ArrayDeque<>();
        
        for (int h = 0; h < H; h++) {
            for (int w = 0; w < W; w++) {
                if (A[h][w] == BLACK) {
                    countB++;
                    qh.add(h);
                    qw.add(w);
                }
            }
        }
        
        int[] mh = {0, 1, 0, -1};
        int[] mw = {1, 0, -1, 0};
        
        while (countB < H*W) {
            List<Integer> lh = new ArrayList<>();
            List<Integer> lw = new ArrayList<>();
            while (!qh.isEmpty()) {
                lh.add(qh.poll());
                lw.add(qw.poll());
            }
            
            for (int ih = 0; ih < lh.size(); ih++) {
                for (int i = 0; i < mh.length; i++) {
                    int nh = lh.get(ih) + mh[i];
                    int nw = lw.get(ih) + mw[i];
                    if (0 <= nh && nh < H && 0 <= nw && nw < W && A[nh][nw] == WHITE) {
                        qh.add(nh);
                        qw.add(nw);
                        countB++;
                        A[nh][nw] = BLACK;
                    }
                }
            }
            ans++;
        }
        
        System.out.println(ans);
    }
    
    private static int nint() {
        return sc.nextInt();
    }

    private static int[] nints(int n) {
        return nints(n, 0, 0);
    }

    private static int[] nints(int n, int padL, int padR) {
        int[] a = new int[padL + n + padR];
        for (int i = 0; i < n; i++)
            a[padL + i] = nint();
        return a;
    }

    private static long nlong() {
        return sc.nextLong();
    }

    private static long[] nlongs(int n) {
        return nlongs(n, 0, 0);
    }

    private static long[] nlongs(int n, int padL, int padR) {
        long[] a = new long[padL + n + padR];
        for (int i = 0; i < n; i++)
            a[padL + i] = nlong();
        return a;
    }

    private static double ndouble() {
        return sc.nextDouble();
    }
    
    private static double[] ndoubles(int n) {
        return ndoubles(n, 0, 0);
    }
    
    private static double[] ndoubles(int n, int padL, int padR) {
        double[] d = new double[n + padL + padR];
        for (int i = 0; i < n; i++) {
            d[padL + i] = ndouble();
        }
        return d;
    }

    private static String nstr() {
        return sc.next();
    }

    private static char[] nchars() {
        return sc.next().toCharArray();
    }

    private static char[] nchars(int padL, int padR) {
        char[] temp = sc.next().toCharArray();
        char[] ret = new char[temp.length + padL + padR];
        System.arraycopy(temp, 0, ret, padL, temp.length);
        return ret;
    }
    
    private static char[][] nchars2(int h, int w) {
        return nchars2(h, w, 0, 0);
    }

    private static char[][] nchars2(int h, int w, int padLU, int padRD) {
        char[][] a2 = new char[h + padLU + padRD][w + padLU + padRD];
        for (int i = 0; i < h; i++)
            System.arraycopy(nchars(), 0, a2[padLU + i], padLU, w);
        return a2;
    }
    
    private static long min(long... ls) {
        return Arrays.stream(ls).min().getAsLong();
    }
    
    private static long max(long... ls) {
        return Arrays.stream(ls).max().getAsLong();
    }
}