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 typesof 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.