미니골프

당신은 $R\times C$ 격자에서 미니골프를 한다. 한 번의 퍼트로 골프공을 위, 아래, 오른쪽, 왼쪽 네 방향 중 하나로 $K$칸까지 원하는 만큼 굴릴 수 있다. 물론 벽을 통과하거나 코스 밖으로 공을 굴릴 수는 없다.

공을 홀에 넣는 데 필요한 최소 퍼트 수를 구하시오.

첫째 줄에 세 정수 $R$, $C$, $K$가 주어진다 ($1 \le R\times C \le 1\,000\,000$이고 $1\le K \le 1\,000\,000$). 이는 각각 행의 수, 열의 수, 공을 굴릴 수 있는 최대 거리이다.

다음 $R$개의 줄에는 각각 $C$개의 문자가 주어지며 미니골프 코스를 나타낸다.

• "."는 빈 칸을 나타낸다.
• "#"는 벽이 있는 칸을 나타낸다.
• "S"는 시작 칸을 나타낸다. 입력에는 "S"가 정확히 하나 있다.
• "G"는 홀이 있는 칸을 나타낸다. 입력에는 "G"가 정확히 하나 있다.

시작 칸에서 홀에 도달할 수 있음이 보장된다.

공을 홀에 넣는 데 필요한 최소 퍼트 수를 정수로 출력한다.