Problem: 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.

Input

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.

Output

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.

Examples

Input

5 3 2
Sba
ccc
aac
ccc
abT


Output

bcccc


Input

3 4 1
Sxyy
yxxx
yyyT


Output

xxxx


Input

1 3 3
TyS


Output

y


Input

1 4 1
SxyT


Output

-1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int dirx[4] = {-1, 0, 0, 1};
int diry[4] = {0, -1, 1, 0};
int qx[100001], head, tail, qy[100001];
int ena[100001], ech[100001];
int stx, sty, enx, eny;
int res;
char ress[3001], s[3001];
int n, m, k;
char g[100][100];
int ans[3001];
int f[100][100];
int now;
int vis[100][100];
inline void work() {
  now++;
  g[stx][sty] = ech[1];
  qx[head = tail = 0] = enx, qy[0] = eny;
  memset(f, 63, sizeof(f));
  f[enx][eny] = 0;
  while (head <= tail) {
    int x = qx[head], y = qy[head++];
    for (int i = 0; i < 4; ++i) {
      int xx = x + dirx[i], yy = y + diry[i];
      if (xx < 0 || yy < 0 || xx >= n || yy >= m || !ena[g[xx][yy]]) continue;
      if (f[xx][yy] > f[x][y] + 1) {
        f[xx][yy] = f[x][y] + 1;
        qx[++tail] = xx, qy[tail] = yy;
      }
    }
  }
  if (f[stx][sty] > res) return;
  memset(ans, 63, sizeof(ans));
  ans[f[stx][sty]] = ech[1];
  qx[head = tail = 0] = stx, qy[0] = sty;
  while (head <= tail) {
    int x = qx[head], y = qy[head++];
    if (ans[f[x][y]] != g[x][y]) continue;
    for (int i = 0; i < 4; ++i) {
      int xx = x + dirx[i], yy = y + diry[i];
      if (xx < 0 || yy < 0 || xx >= n || yy >= m || !ena[g[xx][yy]]) continue;
      if (f[xx][yy] == f[x][y] - 1 && vis[xx][yy] != now) {
        ans[f[xx][yy]] =
            ((ans[f[xx][yy]]) < (g[xx][yy]) ? (ans[f[xx][yy]]) : (g[xx][yy]));
        qx[++tail] = xx, qy[tail] = yy;
        vis[xx][yy] = now;
      }
    }
  }
  int sn = 0;
  for (int i = f[stx][sty] - 1; i > 0; --i) s[sn++] = ans[i] + 'a';
  s[sn] = 0;
  if (res > f[stx][sty] || res == f[stx][sty] && strcmp(s, ress) == -1)
    res = f[stx][sty], memcpy(ress, s, sizeof(s));
}
inline void dfs(int p, int la) {
  if (p > k) {
    work();
    return;
  }
  for (int i = la; i < 26; ++i) {
    ena[i] = 1;
    ech[p] = i;
    dfs(p + 1, i + 1);
    ena[i] = 0;
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%s", g[i]);
    for (int j = 0; j < m; ++j)
      if (g[i][j] == 'S')
        stx = i, sty = j;
      else if (g[i][j] == 'T')
        enx = i, eny = j;
      else
        g[i][j] -= 'a';
  }
  res = 214748364;
  dfs(1, 0);
  if (res == 214748364)
    printf("-1\n");
  else
    printf("%s\n", ress);
  return 0;
}