AT_qupc2018_c Ito Campus

牛君在一个 $H$ 行 $W$ 列的迷宫，其中 `S` 表示牛君的起点，`G` 表示牛君的终点， `#` 表示墙壁，`@` 表示野猪，`.` 表示空地。其中墙壁不可通行，且要求在任意时刻，牛君不可以在 $X$ 步内（含 $X$ 步）走到任意野猪的位置，求牛君从起点到终点的最短路径长度。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ X $ $ s_{11}...s_{1W} $ $ : $ $ s_{H1}...s_{HW} $

输出一个整数表示最短路径长度，如果不可能走到终点，输出 $-1$。

### 制約 - $ 4\ \leq\ H,\ W\ \leq\ 10^3 $ - $ 0\ \leq\ X\ \leq\ 10^6 $ - $ s_{ij} $ は `S` または `G` または `#` または `.` または `@` からなる - スタート地点とゴール地点はそれぞれ $ 1 $ つずつ存在する - イノシシがいるマスは $ 1 $ つ以上存在する - スタート地点は安全なマスであることが保証されている - 迷路の外側 $ 1 $ マスは壁で囲われている - $ H,W,X $ は整数 ### 部分点 - $ H,\ W\ \leq\ 50 $ を満たすデータセットに正解した場合、$ 30 $ 点が与えられる。 ### Sample Explanation 1 $ (2,2) $ → $ (3,2) $ → $ (3,3) $ → $ (4,3) $ → $ (4,4) $ → $ (5,4) $ と移動することで、スタートから安全なマスのみを通ってゴールまで $ 5 $ 回で移動できます。 ### Sample Explanation 3 ゴールが安全なマスとは限りません。