문제

알고리즘 동아리에서 공부하던 승우는 깜빡 잠이 들어 아주 이상한 꿈을 꾸게 되었다! 꿈속에서 승우는 $N \times M$ 크기의 격자 모양 미로에 갇혀 있다. ($1 \le N, M \le 1\,000$) 승우는 현재 왼쪽 위 칸에 있으며, 오른쪽 아래 칸으로 탈출하려고 한다. 승우는 현재 위치에서 상하좌우로 인접한 네 방향 중 한 곳으로 이동할 수 있다.

미로의 각 타일은 색깔이 칠해져 있으며, 색깔마다 다음과 같은 특별한 성질이 있다.

• 빨간색 (0): 지나갈 수 없는 벽이다.
• 분홍색 (1): 평범하게 지나갈 수 있는 타일이다.
• 주황색 (2): 평범하게 지나갈 수 있지만, 이 타일을 밟는 순간 승우의 몸에서 오렌지 향기가 나게 된다.
• 파란색 (3): 피라냐가 살고 있는 타일이다. 승우의 몸에서 오렌지 향기가 날 때만 이 타일을 지날 수 있다.
• 보라색 (4): 이 타일을 밟으면 승우는 이전에 이동하던 방향으로 미끄러진다. 보라색 타일을 밟는 순간 승우의 몸에서 나던 오렌지 향기는 즉시 사라진다. 승우는 다음 상황 중 하나를 마주할 때까지 계속 미끄러진다.
  • 이동할 수 없는 칸(빨간색 타일, 혹은 향기가 없는 상태에서 파란색 타일)에 부딪힐 때
  • 미로의 경계를 벗어날 때
  • 보라색이 아닌 타일에 도착할 때

만약 이동할 수 없는 칸에 부딪히거나 경계를 벗어나 미끄러짐이 멈춘다면, 승우는 그 직전 칸에 멈추게 된다. 만약 멈춘 칸이 다시 보라색 타일이라면, 승우는 그 타일에서 다시 미끄러지기 시작한다. 미끄러지며 통과하는 모든 칸(보라색 타일 포함)은 각각 이동 횟수 $1$로 계산한다.

승우가 왼쪽 위 칸에서 출발하여 오른쪽 아래 칸까지 도달하는 데 필요한 최소 이동 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 미로의 행 개수 $N$과 열 개수 $M$이 공백으로 구분되어 주어진다. ($1 \le N, M \le 1\,000$)

이어서 $N$개의 줄에 걸쳐 각 줄마다 미로의 상태를 나타내는 $M$개의 정수가 공백으로 구분되어 주어진다.

• 0: 빨간색 타일
• 1: 분홍색 타일
• 2: 주황색 타일
• 3: 파란색 타일
• 4: 보라색 타일

왼쪽 위와 오른쪽 아래 칸은 항상 분홍색(1)이다.

출력

승우가 미로를 통과하기 위해 필요한 최소 이동 횟수를 출력한다. 만약 오른쪽 아래 칸에 도달할 수 없다면 -1을 출력한다.

예제 입력 1

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

예제 출력 1

10