{"raw_statement":[{"iden":"statement","content":"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.\n\nThe 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.\n\nYour 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."},{"iden":"input","content":"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_.\n\nPretest 12 is one of the maximal tests for this problem."},{"iden":"output","content":"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**.\n\n**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."},{"iden":"examples","content":"Input\n\n5 3 2\nSba\nccc\naac\nccc\nabT\n\nOutput\n\nbcccc\n\nInput\n\n3 4 1\nSxyy\nyxxx\nyyyT\n\nOutput\n\nxxxx\n\nInput\n\n1 3 3\nTyS\n\nOutput\n\ny\n\nInput\n\n1 4 1\nSxyT\n\nOutput\n\n\\-1"}],"translated_statement":[{"iden":"statement","content":"你已经知道瓦列里的最爱运动是冬季两项。在你的帮助下，他学会了射击时从不失手，射击技巧无人能及。但现在他需要完成一个更小的任务：学会以最快速度完成赛道。\n\n赛道的地图是一个大小为 #cf_span[n × m] 的矩形，被划分为若干方格。每个方格用一个小写拉丁字母标记（表示该地块的类型），但起始方格（用大写拉丁字母 #cf_span[S] 标记）和终止方格（用大写拉丁字母 #cf_span[T] 标记）除外。从一个方格移动到另一个方格耗时 #cf_span[1] 分钟。在方格内部移动的时间可忽略不计。我们只能移动到相邻的方格（上下左右），但禁止移出地图边界。此外，路径需满足以下限制：访问的不同类型方格的数量不得超过 #cf_span[k] 个（同一类型的方格可以无限次访问）。标记为 #cf_span[S] 和 #cf_span[T] 的方格没有类型，因此不计入类型计数。但 #cf_span[S] 必须恰好访问一次——在路径开始时，#cf_span[T] 必须恰好访问一次——在路径结束时。\n\n你的任务是找到从方格 #cf_span[S] 到方格 #cf_span[T] 的最短时间路径。在所有最短路径中，你需要选择字典序最小的一条。比较路径时，应将它们表示为由地块类型字符组成的序列。\n\n第一行输入包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n, m ≤ 50, n·m ≥ 2, 1 ≤ k ≤ 4]）。接下来 #cf_span[n] 行包含地图。每行恰好包含 #cf_span[m] 个字符，由小写拉丁字母和字符 #cf_span[S]、#cf_span[T] 组成。保证地图中恰好包含一个 #cf_span[S] 和一个 #cf_span[T]。\n\n预测试 12 是本题的最大测试用例之一。\n\n如果存在满足条件的路径，请将其作为由字母组成的序列输出——即地块类型。否则，输出 \"-1\"（不含引号）。*你不应输出开头的 #cf_span[S] 字符和结尾的 #cf_span[T] 字符*。\n\n*注意：该序列可能为空*。这种情况存在于预测试中。你可以什么都不输出，或仅输出一个“换行”字符，两者均可接受。"},{"iden":"input","content":"第一行输入包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ n, m ≤ 50, n·m ≥ 2, 1 ≤ k ≤ 4]）。接下来 #cf_span[n] 行包含地图。每行恰好包含 #cf_span[m] 个字符，由小写拉丁字母和字符 #cf_span[S]、#cf_span[T] 组成。保证地图中恰好包含一个 #cf_span[S] 和一个 #cf_span[T]。预测试 12 是本题的最大测试用例之一。"},{"iden":"output","content":"如果存在满足条件的路径，请将其作为由字母组成的序列输出——即地块类型。否则，输出 \"-1\"（不含引号）。*你不应输出开头的 #cf_span[S] 字符和结尾的 #cf_span[T] 字符*。*注意：该序列可能为空*。这种情况存在于预测试中。你可以什么都不输出，或仅输出一个“换行”字符，两者均可接受。"},{"iden":"examples","content":"输入\n5 3 2\nSbac\ncca\nacccc\nabT\n输出\nbcccc\n\n输入\n3 4 1\nSxyy\nyyxx\nxyyyT\n输出\nxxxx\n\n输入\n1 3 3\nTyS\n输出\ny\n\n输入\n1 4 1\nSxyT\n输出\n-1"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, m \\leq 50 $, $ n \\cdot m \\geq 2 $, $ 1 \\leq k \\leq 4 $.  \nLet $ G = (V, E) $ be a grid graph of size $ n \\times m $, where each cell $ (i, j) $ is a vertex.  \nLet $ \\text{map}[i][j] \\in (\\Sigma \\cup \\{S, T\\}) $ denote the label of cell $ (i, j) $, where $ \\Sigma $ is the set of lowercase Latin letters.  \nLet $ s = (s_i, s_j) \\in V $ be the unique cell with label $ S $.  \nLet $ t = (t_i, t_j) \\in V $ be the unique cell with label $ T $.  \n\n**Constraints**  \n1. Movement is allowed only to 4-directionally adjacent cells (up, down, left, right).  \n2. The path must start at $ s $ and end at $ t $, visiting each exactly once.  \n3. The path may visit any number of cells of the same letter type, but may visit at most $ k $ *distinct* lowercase letter types (i.e., from $ \\Sigma $).  \n4. $ S $ and $ T $ are not counted toward the $ k $ distinct types.  \n5. Among all shortest paths (minimizing number of steps), choose the lexicographically minimal sequence of *visited letter types* (excluding $ S $ and $ T $).  \n\n**Objective**  \nFind a path $ P = (v_0 = s, v_1, \\dots, v_L = t) $ minimizing $ L $ (number of edges), and among all such minimal-length paths, minimize the sequence $ \\sigma = (\\text{map}[v_1], \\text{map}[v_2], \\dots, \\text{map}[v_{L-1}]) $ lexicographically, subject to:  \n- $ |\\{ \\text{map}[v_i] \\mid 1 \\leq i \\leq L-1 \\}| \\leq k $,  \n- $ \\text{map}[v_i] \\in \\Sigma $ for all $ 1 \\leq i \\leq L-1 $.  \n\nOutput $ \\sigma $ if such a path exists; otherwise output \"-1\".","simple_statement":null,"has_page_source":false}