CF83C.Track

You already know that Valery's favorite sport is biathlon. Due to your help, he learned to shoot without missing, and his skills are unmatched at the shooting range. But now a smaller task is to be performed, he should learn to complete the path fastest.

The track's map is represented by a rectangle n × m in size divided into squares. Each square is marked with a lowercase Latin letter (which means the type of the plot), with the exception of the starting square (it is marked with a capital Latin letters S) and the terminating square (it is marked with a capital Latin letter T). The time of movement from one square to another is equal to 1 minute. The time of movement within the cell can be neglected. We can move from the cell only to side-adjacent ones, but it is forbidden to go beyond the map edges. Also the following restriction is imposed on the path: it is not allowed to visit more than k different types of squares (squares of one type can be visited an infinite number of times). Squares marked with S and T have no type, so they are not counted. But S must be visited exactly once — at the very beginning, and T must be visited exactly once — at the very end.

Your task is to find the path from the square S to the square T that takes minimum time. Among all shortest paths you should choose the lexicographically minimal one. When comparing paths you should lexicographically represent them as a sequence of characters, that is, of plot types.

你已经知道瓦列里最喜爱的运动是冬季两项。在你的帮助下，他学会了百发百中地射击，其射击技艺在靶场上无人能及。但现在有一项更小的任务需要完成：他需要学会以最短时间跑完全程。

赛道地图由一个 $n \times m$ 的矩形网格表示，网格被划分为若干方格。每个方格标有一个小写拉丁字母（表示该方格的类型），起始方格除外（它标有大写拉丁字母 S），终点方格也除外（它标有大写拉丁字母 T）。从一个方格移动到另一个相邻方格耗时 1 分钟；而方格内部的移动时间可忽略不计。我们仅可向上下左右四个侧邻方格移动，且禁止移出地图边界。此外，路径还需满足如下限制：路径中所经过的不同类型方格的数量不得超过 $k$ 种（同一类型的方格可被重复访问任意多次）。标有 S 和 T 的方格没有类型，因此不计入类型种类数。但 S 必须恰好访问一次——且只能在路径起点；T 也必须恰好访问一次——且只能在路径终点。

你的任务是找出一条从方格 S 到方格 T 的路径，使其耗时最短。在所有最短路径中，你需要选择字典序最小的一条。比较路径时，应将路径字典序地表示为一个字符序列，即各经过方格的类型所组成的字符串。

The first input line contains three integers n, m and k (1 ≤ n, m ≤ 50, n·m ≥ 2, 1 ≤ k ≤ 4). Then n lines contain the map. Each line has the length of exactly m characters and consists of lowercase Latin letters and characters S and T. It is guaranteed that the map contains exactly one character S and exactly one character T.

Pretest 12 is one of the maximal tests for this problem.

第一行输入包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m \le 50$，$n \cdot m \ge 2$，$1 \le k \le 4$）。接下来 $n$ 行描述地图，每行恰好包含 $m$ 个字符，由小写拉丁字母以及字符 S 和 T 组成。保证地图中恰好包含一个字符 S 和一个字符 T。

预测试用例 12 是本题的极大化测试用例之一。

If there is a path that satisfies the condition, print it as a sequence of letters — the plot types. Otherwise, print "-1" (without quotes). You shouldn't print the character S in the beginning and T in the end.

Note that this sequence may be empty. This case is present in pretests. You can just print nothing or print one "End of line"-character. Both will be accepted.

如果存在一条满足条件的路径，请将其打印为一串字母——即地块类型序列。否则，打印 -1（不带引号）。你不应在开头打印字符 S，也不应在结尾打印字符 T。

注意：该序列可能为空。这种情况出现在预测试中。你可以直接不输出任何内容，或仅输出一个“换行符”（End of line）。两种方式均会被接受。