Древний замок

Кэл Кестис обнаружил древний храм Силы. Вход в храм находится в прямоугольной пещере. Чтобы попасть в храм, нужно открыть рунический замок, которым запечатан вход.

Пещера, в которой находится вход в храм, имеет размеры n×m метров, и поделена на квадраты размера 1 × 1 метр. Представим пещеру в виде таблицы n × m, строки которой пронумерованы от 1 до n сверху вниз, а столбцы — от 1 до m слева направо. В некоторых квадратах находятся рунические камни, а остальные квадраты свободны. Кэл может перемещаться только по свободным квадратам. За единицу времени он может переместиться из квадрата в соседний по стороне.

Сейчас Кэл находится в некотором квадрате пещеры. Чтобы открыть вход в храм, нужно в правильном порядке коснуться нескольких рунических камней. После чего, Кэл должен дойти до квадрата, в котором откроется вход в храм. Чтобы коснуться рунического камня, расположенного в некотором квадрате, Кэл должен встать в квадрате, соседнем по стороне. На то, чтобы коснуться камня, Кэл не тратит дополнительного времени.

За Кэлом гонятся инквизиторы Империи, и он хочет узнать, за какое минимальное время можно открыть замок и войти в храм. Помогите ему узнать эту величину.

Формат входных данных

В первой строке даны три целых числа n, m и k — размеры пещеры и длина последовательности камней, до которых Кэл должен дотронуться (1 ≤ n,m ≤ 100; 0 ≤ k ≤ 100).

В следующих n строках дано по m символов — описание пещеры. Символ «#» соответствует непроходимой клетке, содержащей камень. Все остальные клетки свободны. Символ «S» соответствует квадрату, в котором Кэл находится изначально. А символ «F» соответствует квадрату, в котором откроется вход в храм. Кэл должен будет прийти в него после того, как откроет замок. Все остальные символы равны «.». Гарантируется, что символы «S» и «F» встречаются ровно по одному разу.

В следующих k строках даны по два целых числа x_i и y_i — номер строки и столбца, на пересечении которых находится i-й камень, которого Кэл должен коснуться. Гарантируется, что квадрат на пересечении строки номер x_i и столбца номер y_i содержит камень для всех i от 1 до k.

Формат выходных данных

Если Кэл не сможет открыть замок и войти в храм, выведите число −1. Иначе, выведите минимальное время, необходимое, чтобы открыть замок и дойти до входа в храм.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача	Баллы	Ограничения	Необходимые подзадачи	Информация о проверке
1	11	k = 0		первая ошибка
2	34	k ≤ 5	1	первая ошибка
3	55		1, 2	первая ошибка

Примеры

стандартный ввод		стандартный вывод
3 5 3 #.... ####. FS... 1    1 2    3 2 2	17
3 5 1 #.... ##### FS... 1 1	-1
3 5 0 F#... .#.#. ...#S	10

Замечание

В первом примере, Кэл сначала должен дойти до квадрата (1,2) за 8 шагов. Коснуться камня (1,1). Перейти в соседний справа квадрат. Коснуться камня (2,3). Затем, дойти до квадрата (3,2) за 7 шагов. Коснуться камня (2,2). Перейти в соседний слева квадрат. После чего, его маршрут закончится. Суммарно он потратит 8 + 1 + 7 + 1 = 17 единиц времени.