T minus time to ransom! The WannaCrypt ransomware has struck and it is attacking networks right, left and center. A network is defined by an m*n binary matrix (a),  which has a a[i][j] = 1 if a computer is infected and a[i][j] = 0 if it is not. At the end of each hour, all computers that are a neighbour (which shares a side or a corner with) of an infected computer are infected by the ransomware..

Your job is to calculate the time after which all computers in the network will be infected by the virus.

Also, do keep in mind that the shortest code wins.

Input

The first 2 lines contains the values of m and n respectively.
The next m lines contain a binary string of length n corresponding to the computers of the network.

Output

An integer which is equal to the mumber of hours after which the whole network will be infected by the ransomware.

Input Constraints

1 &lt;= m,n &lt;= 1000

Sample Test Cases

Test Case 1

Sample Input

2
2
11
11


Sample Output

0


Test Case 2

Sample Input

3
4
0101
0001
0001


Sample Output

2


Test Case 3

Sample Input

2
2
10
00


Sample Output

1


P.S: Take input in any format that doesn't violate the ordering of [m,n,matrix]
P.P.S: m and n are optional inputs. The only compulsory input is the matrix.
Python 2, 90 bytes



g=lambda a:min(min(a))or-~g(map(lambda*c:map(max,(0,)+c[:-1],c,c[1:]),*a))
lambda a:g(a)/2


Try it online!

Accepts a matrix as a list of lists of 0 and 1.

How it works

g=lambda a:min(min(a))or…


If the smallest element of the matrix is 1 (it is completely infected), return 1; otherwise…

                        -~g(…                                            )


return 1 plus the recursive result on the following modified matrix…

                            map(lambda*c:…                           ,*a)


for each old column c…

                                         map(max,(0,)+c[:-1],c,c[1:])


produce a new row by zipping max over the down-shifted, original, and up-shifted versions of c.  (map fills in the gap at the end of c[1:] with None, which is falsy and smaller than both 0 and 1.)

Each iteration of g computes all vertical infections, then transposes the matrix.  This way, every 2 iterations of g compute all horizontal, vertical, and diagonal infections.

lambda a:g(a)/2


Because the base case of g with a fully infected matrix gave 1 rather than 0, the parity works out such that floored division by 2 always gives the correct result.