Problem Statement

In the previous "trends and countermeasures for Kadomatsu sequences" problem, the Kadomatsu sequence problem I had been planning to set was guessed, so it seemed all was lost, but instead we have ended up leaving one-dimensional sequences and jumping out onto a two-dimensional grid.

As has appeared many times recently, a "Kadomatsu sequence" is one that satisfies the conditions "the second largest of the lengths of the 3 bamboo stalks is on the left or right side" and "all 3 lengths are different".

Here, you are given a $W\times H$ planar grid in which each cell has a number from $1$ to $9$ written on it.
On these cells, you can move from your current position by 1 cell up, down, left, or right (Manhattan distance 1) per step.
However, the numbers of the 2 most recently visited places and the new cell must, in that order, form a Kadomatsu sequence.

In other words, let $A$ be the history of the numbers of the cells reached, with $A_i$ being the number of the $i$-th cell passed through, and
let $isKadomatsuSequence$ be a function that determines whether a sequence is a Kadomatsu sequence. Then,

$isKadomatsuSequence(A_{i−2},A_{i-1},A_{i})$

Input

$W$ $H$
$M_{1,1}\ M_{2,1} \dots M_{W,1}$
$M_{1,2}\ M_{2,2} \dots M_{W,2}$
$\dots\dots\dots\dots\dots\dots$
$M_{1,H}\ M_{2,H} \dots M_{W,H}$

All input values are integers.
$2\le W \le 100=10^2$
$2\le H \le 100=10^2$
$1\le M_{i,j}\le 9$
$1\le i \le W,1\le j \le H$

Output

Find the minimum number of steps needed to reach the goal from the start.
If the goal cannot be reached under these conditions, output -1.
Print a newline at the end.

Sample

3 3
1 2 3
3 2 1
1 4 1

4

2 2
1 3
2 2

2

4 4
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

-1

3 3
5 4 1
6 6 9
2 8 8

6