Bessie en Camelot tiene un problema: atravesar bosque vigilado por Knights of Ni. Exigen un arbusto para pasar segura. El tiempo importa, debe encontrarlo y llevarlo lo más rápido.

Mapa de cuadrícula cuadrada usual, paralelo a ejes $X$, $Y$, tamaño $W\times H$ ($1 \le W \le 1000$; $1 \le H \le 1000$).

Indica inicio, única casilla de caballeros, todos los arbustos y zonas transitables. Pantanos, acantilados y conejos asesinos bloquean algunas. Sin arbusto no puede pasar la casilla de caballeros.

Solo norte, este, sur, oeste, nunca diagonal, para seguir bien mapa. Cada casilla vecina cuesta un día.

Se garantiza obtener y entregar arbusto. Halla la forma más rápida.

Entrada

Línea $1$: enteros $W$, $H$ con espacio.

Líneas $2..?$: mapa por filas, primera noroeste y última sureste, enteros de oeste a este. Cada nueva fila empieza nueva línea de entrada, máximo 40 enteros separados por espacios. Si $W \le 40$, una línea describe toda fila; si $W > 40$, varias líneas, 40 números por línea salvo quizá última. Ninguna línea describe más de una fila.

Valores:

• 0: casilla transitable.
• 1: casilla intransitable.
• 2: inicio Bessie.
• 3: Knights of Ni.
• 4: arbusto.

Salida

Línea $1$: $D$, mínimo días para conseguir y entregar arbusto.

Ejemplos

Entrada 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

Salida 1

11

Nota

Ancho $8$, alto $4$, empieza tercera fila a pocas casillas de caballeros.

Puede seguir N, W, N, S, E, E, N, E, E, S, S: arbusto noroeste, rodea obstáculos al este y sur a caballeros.