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++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
int dx[] = { 0, 0, -1, 1 };
int dy[] = { 1, -1, 0, 0 };

int main()
{
  int H, W, ans = 0;
  cin >> H >> W;
  vector<vector<int>> M(H, vector<int>(W, -1));
  queue<pair<int, int>> q;
  rep(i, H) rep(j, W) {
    char c;
    cin >> c;
    if (c == '#') {
      M[i][j] = 0;
      q.push({j, i});
    }
  }
  
  while (!q.empty()) {
    auto p = q.front(); q.pop();
    rep(i, 4) {
      int nx = p.first + dx[i], ny = p.second + dy[i];
      if (nx < 0 || nx >= W || ny < 0 || ny >= H || M[ny][nx] != -1) continue;
      M[ny][nx] = M[p.second][p.first]+1;
      ans = max(M[ny][nx], ans);
      q.push({nx, ny});
    }
  }
  cout << ans << endl;

  return 0;
}