불타는 바라레 마을

가상의 적이 쳐들어와 바라레 마을에 불이 났다. 이미 여러 곳이 불타고 있고 불은 빠르게 번진다. 전쟁에서 홀로 살아남은 호르주칸은 마을에 단 한 대뿐인 헬리콥터까지 가서 빠져나가려 한다.

마을은 $n \times m$ 격자다. 시각 $0$에 일부 칸이 불타고 있다. 어떤 칸에 시각 $x$에 불이 붙으면, 변이나 꼭짓점을 맞댄 이웃 여덟 칸에는 시각 $x + k$에 불이 붙는다. 한번 불이 붙은 칸은 계속 불타는 상태로 남는다. 시각 $0$에 호르주칸은 칸 s에 서 있고, 헬리콥터는 칸 t에 있다. 시각 $x$에 호르주칸은 현재 칸에서 상하좌우로 맞닿은 네 칸 중 하나로 옮겨갈 수 있다. 단, 옮겨갈 칸이 시각 $x + 1$에 불타고 있지 않아야 한다. 이동 한 번에 1초가 걸린다.

불을 피해 s에서 t까지 가는 최단 시간을 구하는 프로그램을 작성하라.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에 양의 정수 $n$, $m$, $k$ ($1 \le n, m, k \le 100$)가 주어진다. $n$과 $m$은 격자의 세로와 가로 크기이고, $k$는 불이 번지는 주기다. 이어지는 $n$개의 줄에는 길이가 $m$인 문자열이 하나씩 주어진다. $i$번째 줄의 $j$번째 문자가 칸 $(i, j)$를 나타낸다. 시각 $0$에 불타고 있는 칸은 f로 적혀 있고, f가 하나도 없을 수도 있다. 헬리콥터가 있는 칸은 t, 호르주칸이 서 있는 칸은 s로 적혀 있으며 각각 정확히 하나씩 있다. 나머지 칸은 -로 채워져 있다. 입력의 마지막 줄은 0 0 0이고, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 불을 피해 s에서 t까지 가는 데 걸리는 최단 시간을 한 줄에 출력한다. t에 도달할 수 없으면 Impossible을 출력한다.