빛의 길

$N \times M$ 격자($2 \leq N, M \leq 100$)의 한 칸에 사악한 괴물이 있고, 다른 칸에 있는 레이저 발생기로 괴물을 죽이려고 한다. 레이저 발생기의 위치와 방향은 고정되어 있으므로 레이저를 반사시키려면 거울이 여러 개 필요할 수 있다. 격자에는 장애물이 있고 거울의 개수는 제한되어 있다. 괴물을 죽일 수 있는지 판별하고, 죽일 수 있다면 필요한 거울의 최소 개수를 구하라.

단면 거울에는 두 종류가 있다. P형 거울은 동서 방향에서 45도 또는 225도 각도로 놓을 수 있고, Q형 거울은 135도 또는 315도 각도로 놓을 수 있다. 예를 들어 거울 네 개를 알맞게 놓으면 레이저는 다음과 같이 지나간다.

거울은 단면이므로 위 그림에서 X 표시가 있는 뒷면은 반사하지 않는다. P형 거울 $A$개와 Q형 거울 $A$개가 있다($0 \leq A \leq 10$). 괴물이나 레이저 발생기가 있는 칸에는 거울을 놓을 수 없지만, 레이저는 그 칸을 지나갈 수 있다. 레이저가 괴물이 있는 칸에 도달하면 괴물은 죽는다.

각 테스트 케이스는 여러 줄로 이루어진다.

첫째 줄에는 세 정수 $N$, $M$, $A$가 주어진다. 다음 $N$개 줄에는 각각 $M$개 문자가 주어지며 격자 정보를 나타낸다. '#', '.', 'S', 'G'는 각각 장애물, 빈 칸, 레이저 발생기의 위치, 사악한 괴물의 위치를 나타낸다. 첫째 줄은 가장 북쪽 칸의 정보를, 마지막 줄은 가장 남쪽 칸의 정보를 나타낸다. 레이저 발생기와 괴물은 각각 정확히 하나씩 있으며, 레이저 발생기는 항상 남쪽으로 레이저를 발사한다.

괴물을 죽일 수 있으면 사용한 거울의 최소 개수를, 아니면 -1을 출력한다.