I. Vanishing Island
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the enchanting realm of Alf Layla w Layla, there lies a remote island where rising sea levels, due to melting ice caps, are increasing the water level by $$$1mm$$$ each year.

The island inhabitants, with a knack for a living simply and no known talent for bridge-building, are worried about their island splitting into separate landmasses. They joke that if their island splits, they might need to start a swimming club just to visit neighbors! Thus, they're keen to find out in which year that will happen.

Fortunately, the wise sorceress Zahra has foreseen this calamity. Using her mystical powers, she has devised a way to predict the fate of the island. She has transformed the island's topography into an $$$n \times m$$$ grid, where each cell represents the elevation above sea level in millimeters (cells with $$$0$$$ elevation initially represent sea). Zahra's magic allows her to simulate the rising sea levels year by year, revealing how the island will change over time.

For the purposes of this problem, an island is considered divided if there exists one path of sea ($$$0$$$ elevation) that separates the island into distinct land masses.

Note that two cells are considered part of the same landmass only if they are connected by their sides (up, down, left, or right).

Furthermore, any land that reaches an elevation below $$$0$$$ is considered submerged and thus treated as sea, even if it doesn't have direct contact with the existing sea areas at that point in time.

If no division occurs, the entire island will eventually sink below sea level.

Zahra's prediction depends on this simulation. She tasks you with analyzing the grid, year by year, as the sea level rises, to determine the precise moment when the island first splits into separate landmasses.

Print the year when the island is first divided into two or more landmasses. If no division occurs until the moment the whole island sinks undersea, print $$$-1$$$.

Input

The first line contains $$$2$$$ integers $$$n$$$ and $$$m$$$ $$$(3 \le n,m \le 10^3)$$$ respectively the length and width of the map containing the island.

Then a grid of $$$n \times m$$$ numbers will follow representing the current topology of the island.

Each number represents the elevation of that point above the sea level while $$$0$$$ represents points already submerged by the sea ($$$0 \leq elevation(i,j) \leq 10^9$$$).

Output

Print the year when the island is first divided into two or more land masses. If no division occurs until the moment the whole island sinks undersea, print $$$-1$$$.

Examples
Input
5 6
0 0 0 0 0 0
0 2 2 1 0 0
0 0 1 1 2 0
0 0 0 2 3 0
0 0 0 0 0 0
Output
1
Input
5 5
0 0 0 0 0
0 0 1 0 0
0 4 2 2 0
0 0 3 0 0
0 0 0 0 0
Output
2
Note

Below is a simulation of the $$$1st$$$ test example

The answer is $$$1$$$ since after $$$1$$$ year the island will be divided into $$$2$$$ isolated landmasses.