Bessie está en Camelot y se ha encontrado en una situación incómoda: ella necesita pasar a través del bosque que es vigilado por los Caballeros de Ni. Para que ella pueda pasar con seguridad, los Caballeros han demandado que ella les lleve una sola fresa. El tiempo es esencial, y Bessie debe encontrar y llevarles una fresa tan pronto como sea posible.

Bessie tiene un mapa del bosque, el cual está particionado en un arreglo cuadrado arreglado en la manera usual, con los ejes paralelos a los ejes ~X~ y ~Y~. El mapa tiene tamaño ~W~ x ~H~ unidades ~(1 \leq W \leq 1000; 1 \leq H \leq 1000)~.

El mapa muestra donde Bessie comienza su recorrido, el único cuadrado en donde están los Caballeros de Ni, y la ubicación de todas las fresas en el territorio. También muestra que áreas del mapa pueden ser atravesadas (algunos bloques del arreglo son impasables debido a pantanos, montañas y conejos asesinos). Bessie no puede pasar a través del cuadrado de los Caballeros de Ni sin una fresa.

Para estar seguros que Bessie siga el mapa correctamente, Bessie puede moverse únicamente en cuatro direcciones: Norte, Este, Sur, U oeste (esto es diagonalmente NO). Ella requiere un día para completar un recorrido de un bloque del arreglo a un bloque vecino del arreglo.

Se garantiza que Bessie será capaz de conseguir una fresa y luego llevarla a los Caballeros de Ni. Determine la manera más rápida en que ella pueda hacer eso.

Entrada

• Línea ~1:~ Dos enteros separados por espacio ~W~ y ~H~.
• Líneas ~2..?:~ Estas líneas describen el bosque, fila por fila. La primera línea describe la parte más al noroeste del bosque.
• La última línea describe la parte más sudeste del bosque. Enteros sucesivos en la entrada describen columnas del bosque de oeste a este. Cada nueva fila de la descripción del bosque comienza en una nueva línea de entrada, y cada línea de la entrada contiene no más de 40 enteros separados por espacios. Si ~W~ \leq 40, entonces cada línea de la entrada describe una fila completa del bosque. Si ~W~ > 40, entonces más de una línea es usada para describir una sola fila, 40 enteros en cada línea exceptuando potencialmente la última. Ninguna línea de la entrada describirá elementos de más de una fila.

Los enteros que describen el bosque vienen de este conjunto:

0: Cuadrado a través del cual Bessie puede desplazarse.

1: Cuadrado impasable, a través del Cual Bessie no puede desplazarse.

2: Posición inicial de Bessie.

3: Posición de los Caballeros de Ni.

4: Posición de una fresa.

Entrada

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

Detalles de la Entrada

Ancho=8, alto=4. Bessie comienza en la tercera fila, solo unos cuadrados lejos de los Caballeros.

Salida

• Línea ~1:~ ~D~, el mínimo número de días que le tomará a Bessie llegar a una fresa y llevársela a los Caballeros de Ni.

Ejemplo de Salida

11

Detalles de la Salida

Bessie puede moverse en este patrón para llevar una frase a los Caballeros: N, O, N, S, E, E, N, E, E, S, S. Ella consigue la fresa en la esquina noroeste y luego rodea las barreras hacia el este y luego al sur hacia los Caballeros.