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