Bessie in Camelot hat ein Problem: den Wald der Knights of Ni durchqueren. Für sicheren Durchgang fordern sie einen Strauch. Zeit drängt, sie muss ihn schnellstmöglich finden und bringen.

Die Karte ist ein übliches quadratisches Gitter parallel zu $X$- und $Y$-Achsen, Größe $W\times H$ ($1 \le W \le 1000$; $1 \le H \le 1000$).

Sie zeigt Start, einziges Ritterfeld, alle Sträucher und begehbare Flächen. Sümpfe, Klippen und Killerkaninchen sperren manche. Ohne Strauch darf sie das Ritterfeld nicht passieren.

Zum korrekten Kartenfolgen nur Nord, Ost, Süd, West, nie diagonal. Zum Nachbarfeld braucht sie einen Tag.

Erhalt und Lieferung eines Strauchs sind möglich. Bestimme den schnellsten Weg.

Eingabe

Zeile $1$: ganze Zahlen $W$, $H$ mit Leerzeichen.

Zeilen $2..?$: Karte zeilenweise, erste nordwestlich, letzte südöstlich, Zahlen west nach ost. Neue Kartenzeile beginnt neue Eingabezeile mit höchstens 40 ganzen Zahlen mit Leerzeichen. Bei $W \le 40$ beschreibt eine eine volle Zeile; bei $W > 40$ mehrere Zeilen, 40 Zahlen jeweils außer möglicherweise zuletzt. Eine Eingabezeile enthält nie mehrere Kartenzeilen.

Werte:

• 0: begehbar.
• 1: unbegehbar.
• 2: Bessies Start.
• 3: Knights of Ni.
• 4: Strauch.

Ausgabe

Zeile $1$: $D$, minimale Tage für Erhalt und Lieferung.

Beispiele

Eingabe 1

8 4
4 1 0 0 0 0 1 0
0 0 0 1 0 1 0 0
0 2 1 1 3 0 4 0
0 0 0 4 1 1 1 0

Ausgabe 1

11

Hinweis

Breite $8$, Höhe $4$, Start in dritter Zeile nur wenige Felder entfernt.

Mögliche Folge N, W, N, S, E, E, N, E, E, S, S: Strauch nordwestlich, Hindernisse nach Osten umgehen, dann Süden zu Rittern.