Một trò chơi đánh golf trên smartphone được mô phỏng là một lưới ô vuông có kích thước ~R~ dòng và ~C~ cột. Cho biết vị trí ô chứa bóng, vị trí ô chứa hố cần đánh bóng vào và vị trí của ô có vật cản. Tại mỗi lần chơi, người chơi có thể đánh quả bóng theo một trong bốn hướng (trên, dưới, trái, phải), quả bóng có thể di chuyển không quá ~K~ ô liên tiếp và không thể đi qua ô có vật cản.

Yêu cầu: Hãy tính số lần đánh bóng ít nhất để đưa được bóng vào hố.

Dữ liệu vào từ tệp văn bản GOLF.INP:

• Dòng đầu tiên gồm ba số nguyên dương ~R, C~ và ~K~ ~(R \times C \le 10^6; \ K \le 10^6)~;
• ~R~ dòng tiếp theo, mỗi dòng chứa ~C~ kí tự thuộc bốn loại kí tự sau:
  • . là vị trí ô trống;
  • # là vị trí ô có vật cản;
  • S là vị trí của bóng, có duy nhất một kí tự S trong bảng;
  • G là vị trí của hố, có duy nhất một kí tự G trong bảng.

Dữ liệu đảm bảo luôn có cách đưa bóng vào hố.

Kết quả ghi ra tệp văn bản GOLF.OUT:

Gồm một số nguyên duy nhất là số lần đánh bóng ít nhất cần thực hiện.

Ví dụ

Input

2 5 1
S#...
...#G

Output

7

Input

2 5 10
S#...
...#G

Output

5

Ràng buộc

• Có ~20\%~ số test ứng với ~20\%~ số điểm không có kí tự # trong bảng;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~R \le 2~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~R, C, K \le 10^2~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~K \ge \max(R, C)~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc gì thêm.