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

class Main{
  public static void main(String[] args){
	Scanner sc = new Scanner(System.in);
    int h = Integer.parseInt(sc.next());
    int w = Integer.parseInt(sc.next());
    char[][] map = new char[h][w];
    int[][] dist = new int[h][w];
    Queue<Pair> queue = new ArrayDeque<>();
    for(int i=0;i<h;i++){
      map[i] = sc.next().toCharArray();
      for(int j=0;j<w;j++){
        dist[i][j] = -1;
        if(map[i][j] == '#'){
          dist[i][j] = 0;
          queue.add(new Pair(i,j));
        }
      }
    }
    int[][] vec = {{1,0},{-1,0},{0,1},{0,-1}};
    int ans = 0,size,yto,xto;
    Pair p;
    while(!queue.isEmpty()){
      ans++;
      size = queue.size();
      for(int i=0;i<size;i++){
        p = queue.poll();
        for(int j=0;j<4;j++){
          yto = p.y + vec[j][0];
          xto = p.x + vec[j][1];
          if(yto>=0 && yto<h && xto>=0 && xto <w && dist[yto][xto]==-1 &&
             map[yto][xto] == '.'){
            dist[yto][xto] = ans;
            queue.add(new Pair(yto,xto));
          }
        }
      }
    }
    System.out.println(ans-1);
    
  }
}
class Pair{
  int x;
  int y;
  public Pair(int y,int x){
    this.x = x;
    this.y = y;
  }
}