Después de comer tanta fruta en la cocina del IPVCE, Dosberto está teniendo algunos sueños extraños! En su sueño más reciente, él está atrapado en un laberinto en la forma de una grilla de \(N×M\) baldosas \((1\leN,M\le1,000)\). Él comienza en la baldosa superior-izquierda y quiere llegar a la baldosa inferior-derecha. Cuando el está parado en una baldosa, pude moverse potencialmente a cualquier baldosa adyacente en cualquiera de las cuatro direcciones cardinales.

¡Pero espere! Cada baldosa tiene un color, y cada color tiene una propiedad diferente! La cabeza le duele a Dosberto simplemente de pensar en eso:

• Si una baldosa es ~roja~, entonces es impasable.
• Si una baldosa es ~rosada~, entonces se puede caminar en ella normalmente.
• Si una baldosa es ~naranja~, entonces se puede caminar en ella normalmente, pero dejará a Dosberto oliendo a naranjas.
• Si una baldosa es ~azul~, entonces contendrá pirañas que dejaran pasar a Dosberto solamente si él huele a naranjas.
• Si una baldosa es ~purpura~, entonces Dosberto saltará a la siguiente baldosa en esa dirección (al menos que no pueda cruzarla). Si esta baldosa también es una baldosa purpura, entonces Dosberto continuará saltando hasta que aterrice en una baldosa no purpura o se estrelle con una baldosa impasable. Saltar encima de una baldosa cuenta como un movimiento. Las baldosas purpuras también le quitan el olor a Dosberto.

(Si usted está confundido con las baldosas purpuras, el ejemplo ilustrará su uso.)

Por favor, ayude a Dosberto a llegar de la baldosa superior-izquierda a la baldosa inferior-derecha en tan pocos movimientos como sea posible.

Formato de entrada:

La primera línea tiene dos enteros ~N~ y ~M~, representando el número de filas y de columnas del laberinto.

Cada una de las siguientes ~N~ líneas contiene ~M~ enteros, representando el laberinto:

• El entero ~'0'~ es una baldosa ~roja~
• El entero ~'1'~ es una baldosa ~rosada~
• El entero ~'2'~ es una baldosa ~naranja~
• El entero ~'3'~ es una baldosa ~azul~
• El entero ~'4'~ es una baldosa ~purpura~

Los enteros de la baldosa superior-izquierda e inferior-drecha siempre serán ~'1'~.

Formato de salida

Un solo entero, representando el número mínimo de movimientos que Dosberto debe hacer para cruzar el laberinto o ~-1~ si es imposible hacerlo.

Entrada de ejemplo:

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

Salida de ejemplo:

10

En este ejemplo, Dosberto camina un cuadrado abajo y dos cuadrados a la derecha (y luego salta un cuadrado más a la derecha). Él camina un cuadrado arriba, un cuadrado a la izquierda y un cuadrado hacia abajo (saltando dos cuadrados hacia abajo) y finaliza caminando un cuadrado más a la derecha. Esto es un total de 10 movimientos