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 long long ll;

int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };

int main() {
  int H,W;
  cin >> H >> W;
  vector< string > A(H);
  vector< vector<int> > d(H, vector<int>(W,-1));
  queue< pair<int,int> > q;
  REP(i,H) {
    cin >> A[i];
    REP(j,W) if (A[i][j] == '#') {
      q.emplace( i,j );
      d[i][j] = 0;
    }
  }
  int ans = 0;
  while ( !q.empty() ) {
    auto v = q.front(); q.pop();
    int y = v.first;
    int x = v.second;
    REP(i,4) {
      int ny = y+dy[i];
      int nx = x+dx[i];
      if ( (ny < 0) || (ny >=H) || (nx < 0) || (nx >= W)) continue;
      if ( d[ny][nx] != -1 ) continue;
      d[ny][nx] = d[y][x]+1;
      q.emplace( ny, nx );
      ans = max(d[ny][nx], ans);
    }
  }
  cout << ans << endl;
}