C. Трасса
ограничение по времени на тест
5 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

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

Карта трассы представляет собой прямоугольник размером n × m разбитый на клетки. Каждая клетка помечена маленькой латинской буквой (которая означает тип участка), исключение составляют клетка-старт (она помечена заглавной латинской буквой S) и клетка-финиш (она помечена заглавной латинской буквой T). Время перехода от одной клетки к другой равно 1 минуте, временем пути внутри клетки можно пренебречь. Из клетки можно перейти только в соседние по стороне, но запрещается выходить за пределы карты. Также на маршрут накладывается ограничение — запрещается посещать более k различных типов клеток (клетки одного типа можно посещать бесконечное количество раз). Клетки, помеченные символами S и T, не имеют типа, поэтому они не считаются. Но клетка S должна быть посещена ровно один раз — в самом начале, и клетка T должна быть посещена ровно один раз — в самом конце.

Ваша задача найти кратчайший по времени маршрут из клетки S в клетку T, а из всех кратчайших маршрутов нужно выбрать лексикографически минимальный. При сравнении маршрутов лексикографически следует их представлять как последовательность символов — типов участков.

Входные данные

В первой строке входного файла заданы три целых числа n, m и k (1 ≤ n, m ≤ 50, n·m ≥ 2, 1 ≤ k ≤ 4). Далее в n строках задана карта. Каждая строка имеет длину ровно m символов и состоит из строчных латинских букв и символов S и T. Гарантируется, что карта содержит ровно один символ S и ровно один символ T.

Претест 12 является одним из максимальных тестов в этой задаче.

Выходные данные

Если существует путь, удовлетворяющий условию, выведите его как последовательность символов — типов участков, символ S в начале и символ T в конце выводить не следует. Иначе выведите «-1» (без кавычек).

Обратите внимание, что эта последовательность может быть пустой. Этот случай присутствует в претестах. Вы можете ничего не выводить или выводить один символ конца строки. Оба варианта будут засчитаны за правильный ответ.

Примеры
Входные данные
5 3 2
Sba
ccc
aac
ccc
abT
Выходные данные
bcccc
Входные данные
3 4 1
Sxyy
yxxx
yyyT
Выходные данные
xxxx
Входные данные
1 3 3
TyS
Выходные данные
y
Входные данные
1 4 1
SxyT
Выходные данные
-1