Camelot의 Bessie는 Knights of Ni가 지키는 숲을 지나야 합니다. 안전 통행 조건은 관목 한 그루입니다. 급하니 가장 빨리 찾아 가져와야 합니다.

지도는 보통 정사각 격자로 $X$, $Y$축과 평행합니다. 크기 $W\times H$ ($1 \le W \le 1000$; $1 \le H \le 1000$)입니다.

시작, 기사들의 단 하나 칸, 모든 관목, 갈 수 있는 곳을 보입니다. 늪, 절벽, 살인 토끼로 일부는 못 갑니다. 관목 없이 기사 칸을 지날 수 없습니다.

지도를 제대로 따라 북동남서 네 방향만(대각선 불가), 인접 칸에 하루입니다.

관목을 얻고 배달할 수 있음이 보장됩니다. 가장 빠른 방법을 구하세요.

입력

$1$번째 줄: 공백 구분 정수 $W$, $H$.

$2..?$번째 줄: 지도 행별로 첫 북서 끝, 마지막 남동 끝이며 수는 서에서 동입니다. 지도 새 행은 입력 새 줄에서 시작하며 줄마다 최대 40 공백 구분 정수입니다. $W \le 40$이면 한 줄에 전체 행, $W > 40$이면 여러 줄이며 마지막은 적을 수 있으나 나머지 40개입니다. 한 입력 줄이 여러 지도 행을 설명하지 않습니다.

값:

• 0: 통행 가능.
• 1: 통행 불가.
• 2: Bessie 시작.
• 3: Knights of Ni.
• 4: 관목.

출력

$1$번째 줄: $D$, 관목을 얻고 배달할 최소 일수.

예제

입력 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

출력 1

11

참고

너비 $8$, 높이 $4$, 셋째 행 시작으로 기사 몇 칸 옆입니다.

N, W, N, S, E, E, N, E, E, S, S로 가서 북서 관목을 얻고 장벽을 동쪽으로 돌아 남쪽 기사에게 갑니다.