문제

인규의 부대에 단풍이 예쁘게 물들었다!

부대는 크기의 격자로 표현되며, 이 중 개의 지점에 나무가 있다. 지점에 높이 의 나무가 있으면 인 , 즉 와 맨하탄 거리가 미만인 지점들에 낙엽이 떨어진다.

말년에는 떨어지는 낙엽도 피하라 했다. 인규는 현재 에 서있으며, 낙엽을 밟지 않으면서 로 최단거리로 이동하려고 한다. 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

입력

첫째 줄에 , , 가 공백으로 구분하여 주어진다.

둘째 줄 부터 개의 줄에 걸쳐 나무의 정보 , , 이 주어진다.

과 에는 낙엽이 없음이 보장된다.

출력

낙엽을 밟지 않으면서 에서 으로 이동하는 최단 거리를 출력한다. 단, 불가능한 경우에는 -1을 출력한다.