Bessie est à Camelot dans une situation délicate : traverser la forêt gardée par Knights of Ni. Ils exigent un seul arbuste pour passer en sécurité. Le temps presse : elle doit le trouver et l'apporter au plus vite.

La carte est un quadrillage carré habituel parallèle aux axes $X$ et $Y$, taille $W\times H$ ($1 \le W \le 1000$; $1 \le H \le 1000$).

Elle indique départ, unique case des chevaliers, tous les arbustes et zones praticables. Marais, falaises et lapins tueurs bloquent certaines cases. Sans arbuste, elle ne peut traverser celle des chevaliers.

Pour bien suivre la carte elle ne va qu'au nord, est, sud, ouest, pas en diagonale. Passer à une case voisine prend un jour.

Obtenir et livrer un arbuste est garanti. Déterminez le trajet le plus rapide.

Entrée

Ligne $1$ : entiers $W$, $H$ séparés par un espace.

Lignes $2..?$ : carte ligne par ligne, première au nord-ouest, dernière au sud-est, entiers de l'ouest à l'est. Une nouvelle ligne de carte commence une nouvelle ligne d'entrée, contenant au plus 40 entiers séparés par des espaces. Si $W \le 40$, elle décrit une ligne entière ; si $W > 40$, plusieurs lignes, 40 entiers chacune sauf éventuellement la dernière. Une ligne d'entrée ne couvre jamais deux lignes de carte.

Valeurs :

• 0 : case praticable.
• 1 : case infranchissable.
• 2 : départ de Bessie.
• 3 : Knights of Ni.
• 4 : arbuste.

Sortie

Ligne $1$ : $D$, minimum de jours pour prendre et livrer l'arbuste.

Exemples

Entrée 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

Sortie 1

11

Remarque

Largeur $8$, hauteur $4$, départ troisième ligne à quelques cases des chevaliers.

Parcours possible N, W, N, S, E, E, N, E, E, S, S : arbuste au coin nord-ouest, contourner les obstacles vers l'est puis sud jusqu'aux chevaliers.