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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

int main() {
  int H,W,A=0;
  cin>>H>>W;
  vector<char> p(H*W);
  queue<int> q;
  vector<int> r(H*W,-1);
  for(int i=0;i<H*W;i++){
    cin>>p.at(i);
    if(p.at(i)=='#'){
      q.push(i);
      r.at(i)=0;
    }
  }
  
  while(!q.empty()){
    int a=q.front();
    q.pop();
    if(r.at(a)>A){
      A++;
    }
    if(a>=W){
      if(r.at(a-W)==-1){
        r.at(a-W)=r.at(a)+1;
        q.push(a-W);
      }
    }
    if(a+W<H*W){
      if(r.at(a+W)==-1){
        r.at(a+W)=r.at(a)+1;
        q.push(a+W);
      }
    }
    if(a%W!=0){
      if(r.at(a-1)==-1){
        r.at(a-1)=r.at(a)+1;
        q.push(a-1);
      }
    }
    if(a%W!=W-1){
      if(r.at(a+1)==-1){
        r.at(a+1)=r.at(a)+1;
        q.push(a+1);
      }
    }
  }
  cout<<A<<endl;
    
}