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

Solution:
INF=float("inf")
def main():
    H,W=map(int, input().split())
    A=[input()for _ in range(H)]
    D=[[0 if A[h][w]=="#" else INF for w in range(W)] for h in range(H)]
    for h in range(H):
        for w in range(1,W):
            D[h][w]=min(D[h][w],D[h][w-1]+1)
        for w in range(W-2, -1, -1):
            D[h][w]=min(D[h][w],D[h][w+1]+1)
    for w in range(W):
        for h in range(1,H):
            D[h][w]=min(D[h][w],D[h-1][w]+1)
        for h in range(H-2, -1, -1):
            D[h][w]=min(D[h][w],D[h+1][w]+1)
    print(max(d for dd in D for d in dd))

if __name__ == "__main__":
    main()