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 <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
  int H, W;
  cin >> H >> W;
  char c;
  vector<vector<int>> A(H, vector<int>(W));
  queue<pair<int,int>> q;
  for (int i = 0; i != H; ++i) {
    for (int j = 0; j != W; ++j) {
      cin >> c;
      if (c == '#') {
        ++A[i][j];
        q.emplace(i,j);
      }
    }
  }

  int ans{-1};
  while (!q.empty()) {
    ++ans;
    int n = q.size();
    for (int i = 0; i != n; ++i) {
      auto [h,w] = q.front();
      q.pop();
      if (h-1 >= 0 && !A[h-1][w]) ++A[h-1][w], q.emplace(h-1,w);
      if (h+1 < H && !A[h+1][w]) ++A[h+1][w], q.emplace(h+1,w);
      if (w-1 >= 0 && !A[h][w-1]) ++A[h][w-1], q.emplace(h,w-1);
      if (w+1 < W && !A[h][w+1]) ++A[h][w+1], q.emplace(h,w+1);
    }
  }
  cout << ans << endl;
}