Вы играете в новую RPG. Карта мира в ней представляет собой клетчатое поле размером n × m клеток. Любой игровой персонаж, стоящий в какой-либо клетке, может переместиться из этой клетки в четырех направлениях — в клетку слева, справа, спереди и сзади, но не выходя за карту мира.
В некоторых клетках живут монстры. Если в какой-то момент времени вы находитесь на клетке, до которой какой-либо из монстров может добраться за d шагов или меньше, он тут же прибежит и убьет вас.
Вам требуется добраться живым из одной клетки игрового поля в другую. Определить, можно ли это сделать, и если да, какое минимальное количество шагов для этого потребуется.
В первой строке даны три неотрицательных числа n, m и d (2 ≤ n·m ≤ 200000, 0 ≤ d ≤ 200000) — размеры поля и максимальное расстояние, на котором монстры опасны.
Каждая из n следующих строк состоит из m символов. Эти символы могут быть равны «.», «M», «S» и «F», что означает пустую клетку, клетку с монстром, стартовую клетку и финишную клетку соответственно. Стартовая и финишная клетки — пустые, и они встречаются ровно один раз.
Если можно добраться из стартовой клетки в финишную живым, выведите минимальное количество шагов, которое для этого нужно сделать. Иначе выведите «-1».
5 7 1
S.M...M
.......
.......
M...M..
......F
12
7 6 2
S.....
...M..
......
.....M
......
M.....
.....F
11
7 6 2
S.....
...M..
......
......
.....M
M.....
.....F
-1
4 4 2
M...
.S..
....
...F
-1
Обратите внимание, что монстры могут прибежать и убить вас как на стартовой, так и на финишной клетке.
