您已经知道瓦莱里最喜欢的运动是冬季两项。在你的帮助下,他学会了射击,而且他的技术在射击场上是无与伦比的。但现在要执行一个较小的任务,他应该学会以最快的速度完成这条路。
赛道的地图由一个大小为 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 是此问题的最大测试之一。
输出
如果存在满足条件的路径,则将其打印为字母序列 - 绘图类型。否则,打印“-1”(不带引号)。您不应该在开头打印字符 S,在结尾打印字符 T。
请注意,该序列可能为空。这种情况出现在预测试中。您可以不打印任何内容或打印一个“行尾”字符。两者都会被接受。
示例
输入 #1
5 3 2 Sba ccc aac ccc abT
输出 #1
bcccc
输入 #2
3 4 1 Sxyy yxxx yyyT
输出 #2
xxxx
输入 #3
1 3 3 TyS
输出 #3
y
输入#4
1 4 1 SxyT
输出#4
-1