Задача C. Исследование Тентуры ≡

Условие

Недавно Плюкианцы решили полностью изучить Тентуру. Для этого они построили очень быстрый пепелац и отправили пацаков в исследовательскую экспедицию. Так как пепелац был очень быстрый, он потреблял много луца, помимо этого, в силу конструктивных особенностей, пепелац не мог летать на большие расстояния, поэтому приходилось приземлятся на каждой планете, которая находилась на траектории полёта. А траектория полёта должна была быть ломаная, отрезки которой, если провести их на карте Тентуры, были параллельны осям координат. При перелёте с одной планеты на другую пепелац потреблял одну единицу луца.

Находясь на одной из исследуемых планет, пацаки заметили, что луца в пепелаце осталось очень мало, они не нашли другого выхода, как попросить вас написать программу, которая, получив карту неисследованной части Тентуры и ещё некоторые данные, рассчитает путь, при котором пацаки исследуют оставшиеся K неисследованных планет и вернутся на Плюк.

Карта неисследованной части Тентуры является прямоугольником ширины W и высоты H. Вся карта разбита на равные квадраты, причём разбиение таково, что в каждом квадрате находится ровно одна планета. Точкой начала отсчёта является левый верхний угол карты. На ней имеются следующие обозначения:

• . — планета известная плюкианцам
• P — планета, которую требуется исследовать
• # — планета, рельеф которой не позволяёт приземляться на неё пепелацу
• S — планета, на которой сейчас находится исследовательский пепелац
• F — планета Плюк

На планетах Тентуры есть E гравицапп. Гравицаппа позволяет перемещаться по Тентуре с огромной скоростью без использования луца. Список планет, где находятся гравицаппы и куда можно попасть при её использовании, прилагается к карте.

Формат входного файла

В первой строке входного файла содержатся числа H W K

Далее следуют H строк по W символов в каждой — карта неисследованной части тентуры

В H + 2-ой строке содержится число E

Далее следуют E строк по четыре числа в каждой: первые два задают планету, на которой есть гравицаппа, вторые два — планету, где оказывается пепелац после её использования (сначала указывается координата по вертикальной оси, затем по горизонтальной). На одной планете может быть несколько гравицапп.

Формат выходного файла

•  − 1 — в случае, если пацаки не смогут вернуться на Плюк, изучив все планеты
• Минимальное количество единиц луца, которое потребуется для исследования всех планет Тентуры и возвращения на Плюк — в противном случае

Ограничения

1 ≤ W, H ≤ 150000

2 ≤ W × H ≤ 150000

0 ≤ K ≤ 10

0 ≤ E ≤ 10⁴

Примеры тестов

3 4 3
.SP.
.##.
FP#P
2
3 1 1 4
2 4 1 3

11