Bessie em Camelot tem um problema: atravessar floresta guardada por Knights of Ni. Exigem um arbusto para passar segura. O tempo urge, deve achar e entregar rapidamente.

Mapa de grade quadrada usual, paralelo aos eixos $X$, $Y$, tamanho $W\times H$ ($1 \le W \le 1000$; $1 \le H \le 1000$).

Mostra início, única casa dos cavaleiros, todos os arbustos e áreas transitáveis. Pântanos, penhascos e coelhos assassinos bloqueiam algumas. Sem arbusto não pode passar na casa dos cavaleiros.

Só norte, leste, sul, oeste, nunca diagonal, para seguir mapa. Cada casa vizinha leva um dia.

É garantido obter e entregar arbusto. Ache o modo mais rápido.

Entrada

Linha $1$: inteiros $W$, $H$ com espaço.

Linhas $2..?$: mapa por linhas, primeira noroeste, última sudeste, inteiros de oeste a leste. Cada nova linha do mapa começa nova linha de entrada, máximo 40 inteiros separados por espaços. Se $W \le 40$, entrada descreve linha completa; se $W > 40$, várias linhas, 40 números cada salvo talvez última. Nenhuma linha de entrada cobre duas linhas do mapa.

Valores:

• 0: casa transitável.
• 1: casa intransitável.
• 2: início Bessie.
• 3: Knights of Ni.
• 4: arbusto.

Saída

Linha $1$: $D$, mínimo dias para obter e entregar arbusto.

Exemplos

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

Saída 1

11

Nota

Largura $8$, altura $4$, inicia terceira linha perto dos cavaleiros.

Pode seguir N, W, N, S, E, E, N, E, E, S, S: arbusto no noroeste, contorna barreiras ao leste e sul aos cavaleiros.