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

public class Main {
    public static void main(String arg[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        boolean visited[][] = new boolean[H][W];
        Queue<Point> q = new LinkedList<>();
        for(int i=0;i<H;i++){
            st = new StringTokenizer(br.readLine());
            String value = st.nextToken();
            for(int j=0;j<W;j++) {
                char c = value.charAt(j);
                if (c == '#') {
                    q.add(new Point(i,j));
                    visited[i][j] = true;
                }
            }
        }
        q.add(new Point(-1,-1));
        int op = 0;
        boolean trigger = false;
        while(!q.isEmpty()){
            Point p = q.poll();
            if(p.H==-1&&p.W==-1){
                if(trigger) {
                    op++;
                    q.add(new Point(-1, -1));
                    trigger = false;
                }
                continue;
            }
            int dr[] = {-1, 0, 0, 1};
            int dc[] = { 0,-1, 1, 0};
            for(int i=0;i<4;i++){
                int nH = p.H+dr[i];
                int nW = p.W+dc[i];
                if(nH<0||nH>=H){
                    continue;
                }
                if(nW<0||nW>=W){
                    continue;
                }
                if(visited[nH][nW]){
                    continue;
                }
                visited[nH][nW] = true;
                q.add(new Point(nH,nW));
                trigger = true;
            }
        }
        System.out.println(op);
    }
}

class Point{
    int H;
    int W;
    Point(int H,int W){
        this.H = H;
        this.W = W;
    }
}