트랙

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" 문자 하나를 출력하면 된다. 둘 다 정답으로 인정된다.