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

Solution:
from collections import deque
def main():
    h, w = map(int, raw_input().split())
    s = [raw_input().strip() for _ in xrange(h)]
    q = deque()
    po = q.popleft
    pu = q.append
    a = [100000] * (h * w)
    for i, r in enumerate(s):
        for j, c in enumerate(r):
            if c == '#':
                pu((i, j))
                a[i*w+j] = 0
    while q:
        x, y = po()
        z = a[x*w+y] + 1
        if x and a[(x-1)*w+y] > z:
            a[(x-1)*w+y] = z
            pu((x-1,y))
        if x < h - 1 and a[(x+1)*w+y] > z:
            a[(x+1)*w+y] = z
            pu((x+1,y))
        if y and a[x*w+y-1] > z:
            a[x*w+y-1] = z
            pu((x,y-1))
        if y < w - 1 and a[x*w+y+1] > z:
            a[x*w+y+1] = z
            pu((x,y+1))
    print z - 1
main()