Задача . C. Трасса

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

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

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