캥거루 소동

산불이 서식지를 위협하고 있습니다. 캥거루인 여러분은 무리의 다른 캥거루에게 가능한 한 빨리 알리고 안전한 지역으로 피해야 합니다.

여러분은 출발점에 가만히 서 있다가 다른 캥거루의 위치로 뜁니다. 각 캥거루가 피할 시간을 충분히 얻도록 정해진 순서대로 방문합니다. 모든 캥거루를 방문한 뒤에는 안전한 지역까지 계속 뛰어가서 그곳에서 멈춥니다.

각 점프에서 북쪽과 동쪽으로 정수 거리만큼 이동하며, 이 거리는 음수일 수도 있습니다. 근력이 제한되어 있어서 한 번의 점프마다 각 방향의 속도를 최대 $1$만큼만 바꿀 수 있습니다. 형식적으로, 점프 $i$에서 북쪽으로 $v_{x,i}$, 동쪽으로 $v_{y,i}$만큼 움직였다면, 점프 $i+1$은 $|v_{x,i+1} - v_{x,i}| \leq 1$이고 $|v_{y,i+1} - v_{y,i}| \leq 1$을 만족해야 합니다.

격자를 벗어나지 않고, 현재 위치에서 다른 캥거루를 모두 거쳐 안전한 지역까지 가는 데 필요한 최소 점프 횟수를 구합니다. 마지막에는 완전히 멈춰야 하므로, 마지막 점프는 안전한 지역에서 출발해 안전한 지역에서 끝나야 합니다.

그림 K.1은 예제 1에서 9번의 점프로 안전한 지역에 도달하는 한 가지 방법을 보여줍니다.

첫 줄에는 격자의 행 수와 열 수인 정수 $r$, $c$($1\leq r, c \leq 50$)와, 경고해야 할 다른 캥거루의 수 $k$($1\leq k\leq 5$)가 주어집니다.

이어서 각각 $c$개의 문자로 이루어진 $r$개의 줄이 주어집니다. .은 빈 칸, #은 뛸 수 없는 덤불입니다. 시작 위치는 0이고, 1부터 k까지의 문자는 이 순서대로 다른 캥거루의 위치를 나타냅니다. k+1 문자는 멈춰야 하는 안전한 지역입니다.

안전한 지역에 도달할 수 있으면 필요한 최소 점프 횟수를 출력합니다. 그렇지 않으면 impossible을 출력합니다.