Minimize Maximum Distance to Fire Station

You are given a grid with (M) rows and (N) columns. Each cell in the grid can be one of the following:

• (0): an empty lot where a fire station can be built.
• (1): a house.
• (2): a park (non-buildable).

Your task is to select an empty cell (containing (0)) to build a fire station such that the maximum Manhattan distance from the fire station to any house is minimized.

The Manhattan distance between two cells ((i_1, j_1)) and ((i_2, j_2)) is given by: [ |i_1 - i_2| + |j_1 - j_2| ]

Find the optimal location for the fire station and report the minimized maximum distance.

inputFormat

Standard input consists of multiple lines. The first line contains two integers (M) and (N) separated by a space, representing the number of rows and columns respectively. The next (M) lines each contain (N) integers separated by spaces, representing the grid. Each integer is either 0, 1, or 2, as described above.

outputFormat

Print a single integer to standard output — the minimum possible maximum Manhattan distance from any house to the nearest fire station.## sample

3 3
1 0 2
0 0 0
2 0 1

2