You play a new RPG. The world map in it is represented by a grid of n × m cells. Any playing character staying in some cell can move from this cell in four directions — to the cells to the left, right, forward and back, but not leaving the world map.
Monsters live in some cells. If at some moment of time you are in the cell which is reachable by some monster in d steps or less, he immediately runs to you and kills you.
You have to get alive from one cell of game field to another. Determine whether it is possible and if yes, find the minimal number of steps required to do it.
The first line contains three non-negative integers n, m and d (2 ≤ n·m ≤ 200000, 0 ≤ d ≤ 200000) — the size of the map and the maximal distance at which monsters are dangerous.
Each of the next n lines contains m characters. These characters can be equal to «_._», «_M_», «_S_» and «_F_», which denote empty cell, cell with monster, start cell and finish cell, correspondingly. Start and finish cells are empty and are presented in the input exactly once.
If it is possible to get alive from start cell to finish cell, output minimal number of steps required to do it. Otherwise, output «_-1_».
Please note that monsters can run and kill you on start cell and on finish cell as well.
## Input
The first line contains three non-negative integers n, m and d (2 ≤ n·m ≤ 200000, 0 ≤ d ≤ 200000) — the size of the map and the maximal distance at which monsters are dangerous.Each of the next n lines contains m characters. These characters can be equal to «_._», «_M_», «_S_» and «_F_», which denote empty cell, cell with monster, start cell and finish cell, correspondingly. Start and finish cells are empty and are presented in the input exactly once.
## Output
If it is possible to get alive from start cell to finish cell, output minimal number of steps required to do it. Otherwise, output «_-1_».
[samples]
## Note
Please note that monsters can run and kill you on start cell and on finish cell as well.
**Definitions**
Let $ n, m, d \in \mathbb{Z}_{\geq 0} $ with $ 2 \leq n \cdot m \leq 200000 $ and $ 0 \leq d \leq 200000 $.
Let $ G = (V, E) $ be a grid graph of size $ n \times m $, where each cell $ (i, j) \in \{1, \dots, n\} \times \{1, \dots, m\} $ is a vertex, and edges connect adjacent cells (up, down, left, right).
Let $ \mathcal{M} \subseteq V $ be the set of monster cells.
Let $ s \in V $ be the unique start cell.
Let $ f \in V $ be the unique finish cell.
Define the *danger zone*:
$$
D = \{ v \in V \mid \exists\, m \in \mathcal{M} \text{ such that } \text{dist}(v, m) \leq d \}
$$
where $ \text{dist}(u, v) $ is the Manhattan distance (shortest path in grid) between $ u $ and $ v $.
**Constraints**
1. $ s \notin \mathcal{M} $, $ f \notin \mathcal{M} $, and both are empty cells.
2. Movement is allowed only to adjacent cells (4-directional).
3. The player cannot enter any cell in $ D $, including $ s $ or $ f $ if they are in $ D $.
**Objective**
Compute the shortest path from $ s $ to $ f $ in $ G \setminus D $, if it exists.
If such a path exists, output its length (number of steps); otherwise, output $ -1 $.