Problem Description

Ushiku and Inoshishi are trapped in a maze.

The maze is represented by a grid of $ H $ rows and $ W $ columns. The cell at the $ i $-th row and $ j $-th column is denoted as $ (i,j) $, and the information of the cell $ (i,j) $ is given by $ s_{ij} $.

• When $ s_{ij} $ is S, the cell $ (i,j) $ is the starting point, and Ushiku is initially in this cell.
• When $ s_{ij} $ is G, the cell $ (i,j) $ is the goal point.
• When $ s_{ij} $ is #, the cell $ (i,j) $ is a wall cell, and it cannot be passed through.
• When $ s_{ij} $ is @, there is an Inoshishi in the cell $ (i,j) $.
• When $ s_{ij} $ is ., the cell $ (i,j) $ is an empty cell.

Ushiku can move to adjacent cells up, down, left, or right, except for wall cells.

A cell is defined as 'safe' if all cells that can be reached within $ X $ moves or fewer from it do not contain any Inoshishi.

Find the minimum number of moves Ushiku needs to reach the goal from the start by only passing through safe cells.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ X $ $ s_{11}...s_{1W} $ $ : $ $ s_{H1}...s_{HW} $

Output Format

Output the minimum number of moves from the start to the goal. If it is impossible to reach the goal from the start by any means, output -1.

Sample Input and Output

Sample Input #1

6 5 1
#####
#S.@#
#...#
#...#
#@.G#
#####

Sample Output #1

5

Sample Input #2

5 6 0
######
#S...#
#@@@.#
#G...#
######

Sample Output #2

8

Sample Input #3

5 5 1
#####
#S..#
#...#
#.@G#
#####

Sample Output #3

-1

Notes/Hints

Constraints

• $4 \leq H, W \leq 10^3$
• $0 \leq X \leq 10^6$
• $ s_{ij} $ consists of S, G, #, ., or @
• There is exactly one starting point and one goal point.
• There is at least one cell with an Inoshishi.
• The starting point is guaranteed to be a safe cell.
• The outer 1-cell layer of the maze is surrounded by walls.
• $ H, W, X $ are integers.

Partial Points

• If you solve the dataset where $H, W \leq 50$, you will be awarded 30 points.

Sample Explanation 1

By moving $ (2,2) $ → $ (3,2) $ → $ (3,3) $ → $ (4,3) $ → $ (4,4) $ → $ (5,4) $, you can reach the goal in 5 moves by only passing through safe cells.

Sample Explanation 3

The goal is not necessarily a safe cell.

见题面 Input 部分

见题面 Output 部分