트랙

Valery가 가장 좋아하는 스포츠가 바이애슬론이라는 것은 이미 알고 있을 것이다. 여러분의 도움 덕분에 그는 빗나가지 않고 사격하는 법을 배웠으며, 사격장에서 그의 실력은 타의 추종을 불허한다. 하지만 이제 더 작은 과제를 수행해야 한다. 그는 코스를 가장 빠르게 완주하는 법을 배워야 한다.

트랙의 지도는 크기가 n × m인 직사각형이며, 정사각형 칸들로 나뉘어 있다. 각 칸에는 소문자 라틴 문자(구간의 유형을 뜻한다)가 표시되어 있다. 단, 시작 칸에는 대문자 라틴 문자 S가, 도착 칸에는 대문자 라틴 문자 T가 표시되어 있다. 한 칸에서 다른 칸으로 이동하는 데 걸리는 시간은 1분이다. 칸 내부에서 이동하는 데 걸리는 시간은 무시할 수 있다. 한 칸에서는 변을 공유하는 칸으로만 이동할 수 있으며, 지도의 경계를 벗어나는 것은 금지된다. 또한 경로에는 다음과 같은 제한이 적용된다. 서로 다른 유형의 칸을 k개보다 많이 방문해서는 안 된다(같은 유형의 칸은 무한히 많이 방문할 수 있다). S and T로 표시된 칸에는 유형이 없으므로 개수에 포함하지 않는다. But S는 맨 처음에 정확히 한 번 방문해야 하며, T는 맨 마지막에 정확히 한 번 방문해야 한다.

여러분의 과제는 S 칸에서 T 칸으로 가는 경로 중 시간이 최소인 경로를 찾는 것이다. 모든 최단 경로 중 사전순으로 가장 작은 경로를 선택해야 한다. 경로를 비교할 때는 경로를 문자, 즉 구간 유형의 수열로 나타내어 사전순으로 비교해야 한다.

입력의 첫째 줄에는 세 정수 n, m, k가 (1 ≤ n, m ≤ 50, n·m ≥ 2, 1 ≤ k ≤ 4) 주어진다. 이어지는 n개의 줄에는 지도가 주어진다. 각 줄의 길이는 정확히 m자이며, 소문자 라틴 문자와 문자 S and T로 이루어진다. 지도에 문자 S가 정확히 하나, 문자 T가 정확히 하나 포함됨이 보장된다.

사전 테스트 12는 이 문제의 최대 크기 테스트 중 하나이다.

조건을 만족하는 경로가 있다면 구간 유형을 나타내는 문자 수열로 출력한다. 그렇지 않다면 "-1"을 따옴표 없이 출력한다. 시작의 문자 S와 끝의 T는 출력하지 않아야 한다.

이 수열은 비어 있을 수도 있음에 유의한다. 이러한 경우가 사전 테스트에 포함되어 있다. 아무것도 출력하지 않거나 "End of line" 문자 하나를 출력하면 된다. 두 방식 모두 정답으로 인정된다.