Bessie w Camelot ma kłopot: musi przejść las Knights of Ni. Żądają pojedynczego krzewu dla bezpiecznego przejścia. Czas nagli, musi znaleźć i dostarczyć najszybciej.

Mapa to zwykła kwadratowa siatka równoległa do osi $X$, $Y$, rozmiar $W\times H$ ($1 \le W \le 1000$; $1 \le H \le 1000$).

Pokazuje start, jedyne pole rycerzy, wszystkie krzewy i przechodnie obszary. Bagna, klify i zabójcze króliki blokują niektóre. Bez krzewu nie przejdzie pola rycerzy.

Dla zgodności z mapą tylko północ, wschód, południe, zachód, nie ukośnie. Sąsiednie pole kosztuje dzień.

Zdobycie i dostawa są gwarantowane. Znajdź najszybszy sposób.

Wejście

Wiersz $1$: całkowite $W$, $H$ ze spacją.

Wiersze $2..?$: mapa wierszami, pierwszy północno-zachodni, ostatni południowo-wschodni, liczby od zachodu na wschód. Nowy wiersz mapy zaczyna nowy wejściowy, najwyżej 40 całkowitych ze spacjami. $W \le 40$ oznacza cały wiersz w jednym; $W > 40$ kilka, po 40 liczb z wyjątkiem być może ostatniego. Wiersz wejścia nigdy nie obejmuje dwóch wierszy mapy.

Wartości:

• 0: przechodnie pole.
• 1: nieprzechodnie.
• 2: start Bessie.
• 3: Knights of Ni.
• 4: krzew.

Wyjście

Wiersz $1$: $D$, minimum dni zdobycia i dostawy.

Przykład

Wejście 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

Wyjście 1

11

Uwagi

Szerokość $8$, wysokość $4$, start trzeci wiersz blisko rycerzy.

Można N, W, N, S, E, E, N, E, E, S, S: krzew północno-zachodni, obejście barier na wschód, potem południe do rycerzy.