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.io.*;
import java.util.*;
public class Main{
    static char[][] A;
    public static void main(String[] args) throws IOException{
        Reader r = new Reader();        
        int[] HW = r.ii();
        int H = HW[0],
            W = HW[1];
        A = new char[H][W];
        HashSet<int[]> queue = new HashSet<>();
        for(int i = 0; i < H; i++){
            String Ai = r.s();
            for(int j = 0; j < W; j++){
                A[i][j] = Ai.charAt(j);
                if(A[i][j] == '#') queue.add(new int[]{i, j});
            }
        }
        int count = 0;
        while(true){
            Iterator<int[]> iterator = queue.iterator();
            HashSet<int[]> queue2 = new HashSet<>();
            while(iterator.hasNext()){
                int[] ij = iterator.next();
                int i = ij[0],
                    j = ij[1];
                turnBlack(i-1, j, queue2);
                turnBlack(i, j-1, queue2);
                turnBlack(i+1, j, queue2);
                turnBlack(i, j+1, queue2);
            }
            if(queue2.size() > 0){
                queue.clear();
                queue.addAll(queue2);
                count++;
            } else{
                break;
            }            
        }
        print(count);
    }
    static void turnBlack(int i, int j, HashSet<int[]> queue){
        try{
            if(A[i][j] == '.'){
                A[i][j] = '#';
                queue.add(new int[]{i, j});
            }
        } catch(ArrayIndexOutOfBoundsException e){}
    }
    static void print(Object o){
        System.out.println(o.toString());
    }
    static class Reader extends BufferedReader{
        Reader(){
            super(new InputStreamReader(System.in));
        }
        String s() throws IOException{
            return readLine();
        }
        String[] ss() throws IOException{
            return readLine().split(" ");
        }
        int[] ii() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            int[] ii = new int[size];
            for(int j = 0; j < size; j++) ii[j] = Integer.parseInt(ss[j]);
            return ii;
        }
    }
}