Optimal Police Station Placement

You are given a grid representing a city of size P rows and Q columns. Each cell in the grid is either a building (denoted by 1) or an open space (denoted by 0).

Your task is to determine the optimal placement of a police station such that the maximum Manhattan distance from the police station to any building is minimized. In other words, if the police station is placed at a cell \( (x,y) \), then for each building at \( (i,j) \) the Manhattan distance \( |x-i| + |y-j| \) is computed, and your goal is to minimize the maximum of these distances.

Formally, if the optimal maximum distance is \( D \), then for every building located at \( (i,j) \) we have:

\[ |x-i|+|y-j| \leq D \]

Your task is to compute and output the smallest such \( D \).

inputFormat

The first line contains two integers (P) and (Q) representing the number of rows and columns of the grid. Each of the next (P) lines contains (Q) integers (each either 0 or 1) separated by spaces indicating the grid's layout, where 1 represents a building and 0 represents an open space.

outputFormat

Output a single integer --- the minimized maximum Manhattan distance from the optimally placed police station to every building.## sample

3 3
1 0 1
0 0 0
1 0 1

2