Problem
보물 사냥꾼 바샤는 고대 던전의 지도를 발견했습니다. 던전은 NM 크기의 미로(1NM100 , NM100)입니다. 미로의 각 셀은 비어 있고 통과할 수 있거나 벽을 포함합니다. 셀에서 벽에 인접한 셀로만 이동할 수 있습니다(예: 각 셀에는 4개 이하의 인접 셀이 있을 수 있음).
셀 중 하나에는 Vasya가 얻고 싶어하는 보물이 있습니다. 미궁에는 Vasya가 여정을 시작할 수 있는 K개의 입구가 있습니다.
보물까지의 이동 거리를 최소화하기 위해 Vasya가 여행을 시작해야 하는 입구를 결정해야 합니다. 이러한 입력이 여러 개인 경우 가장 작은 숫자로 입력을 인쇄합니다.
입력
첫 번째 줄에는 미로의 크기를 정의하는 2개의 숫자 N과 M이 포함되어 있습니다. 미로에 대한 설명은 다음과 같습니다. 각각 M 문자가 있는 N 줄. 0은 셀이 비어 있음을 의미합니다. 1 새장에 벽이 있습니다. 기호 *는 보물이 있는 셀을 나타냅니다(미로에는 정확히 하나의 셀이 있습니다).
(N+2)번째 줄에는 숫자 K(1<=K<= NxM)가 포함되어 있습니다. 즉, 미로의 입구 수입니다. 다음으로 K 라인에는 입력 좌표가 포함됩니다. 따라서 i번째 줄에는 숫자 xi와 yi가 포함되며, 이는 i번째 입력이 xi번째 줄과 yi번째 열(1xiN1yiM)에 있음을 의미합니다. 입력의 좌표가 쌍별로 다르고 모든 입력이 빈 셀에 있음이 보장됩니다. 보물 상자에는 입구가 없습니다.
출력
입력하고자 하는 숫자(1부터 시작)를 하나의 숫자로 표시해야 합니다. 보물에 도달할 수 없으면 -1을 인쇄합니다.
예
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
5 5
<사업부>00000
<사업부>00000
10*00
<사업부>01111
<사업부>00000
<사업부>4
<사업부>1 1
1 5
<사업부>4 1
5 5
|
1 |
| 2 |
3 3
<사업부>010
<사업부>1*1
<사업부>010
<사업부>4
<사업부>1 1
1 3
3 1
3 3
|
-1 |