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>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int> P;

int di[] = {-1, 0, 0, 1};
int dj[] = { 0,-1, 1, 0};

int main(){
  int h,w;
  cin >> h >> w;
  
  vector<string> map(h);
  rep(i,h) cin >> map[i];
  
  queue<P> q;
  rep(i,h) rep(j,w) if(map[i][j] == '#') q.emplace(i,j);
  q.emplace(-1,-1);
  
  int ans = 0;
  while(1){
    int i = q.front().first;
    int j = q.front().second; q.pop();
    if(i == -1 && j == -1){
      if(q.empty()) break;
      ans++; q.emplace(-1,-1);
      continue;
    }
    rep(dir,4){
      int ni = i + di[dir];
      int nj = j + dj[dir];
      if(ni<0||nj<0||ni>=h||nj>=w) continue;
      if(map[ni][nj] == '#') continue;
      map[ni][nj] = '#';
      q.emplace(ni,nj);
    }
  }
  cout << ans << endl;
  return 0;
}