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>
int n, m, u, v, cnt;
int pos[30], dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
char s[60][60], s2[3000], ans[3000], tmp[3000];
int d[3000], in[3000], next[3000], q[1000000 + 1], f, r, mind;
int cmp(int a, int b) {
  int flag = 0;
  while (a != -1 && b != -1) {
    if (s2[a] < s2[b]) {
      flag = -1;
      break;
    } else if (s2[a] > s2[b]) {
      flag = 1;
      break;
    } else {
      a = next[a];
      b = next[b];
    }
  }
  return flag;
}
void spfa(int M) {
  int i, j, nc;
  int cu, nv, x, y, nx, ny;
  memset(d, -1, sizeof(d));
  memset(in, 0, sizeof(in));
  memset(next, -1, sizeof(next));
  f = r = 0;
  q[r++] = v;
  d[v] = 0;
  in[v] = 1;
  while (f != r) {
    cu = q[f];
    in[cu] = 0;
    f = (f + 1) % 1000000;
    x = cu / m;
    y = cu % m;
    for (i = 0; i < 4; i++) {
      nx = x + dir[i][0];
      ny = y + dir[i][1];
      nv = nx * m + ny;
      if (0 <= nx && nx < n && 0 <= ny && ny < m &&
          (nv == u || (M & (1 << pos[s2[nv] - 'a'])) != 0)) {
        if (d[nv] == -1 || d[nv] > d[cu] + 1 ||
            (d[nv] == d[cu] + 1 && cmp(cu, next[nv]) <= 0)) {
          d[nv] = d[cu] + 1;
          next[nv] = cu;
          if (in[nv] == 0) {
            in[nv] = 1;
            q[r] = nv;
            r = (r + 1) % 1000000;
          }
        }
      }
    }
  }
  if (d[u] != -1 && (mind == -1 || mind >= d[u])) {
    cu = u;
    j = 0;
    while (cu != v && cu != -1) {
      tmp[j++] = s2[cu];
      cu = next[cu];
    }
    tmp[j] = '\0';
    if (mind == -1 || mind > d[u] || (mind == d[u] && strcmp(tmp, ans) < 0)) {
      strcpy(ans, tmp);
    }
    mind = d[u];
  }
}
int mask[20000], mm;
void dfs(int i, int state, int k) {
  if (k == 0) {
    mask[mm++] = state;
    return;
  }
  if (i < 0) {
    return;
  }
  dfs(i - 1, state, k);
  state = state | (1 << i);
  dfs(i - 1, state, k - 1);
}
int main() {
  int i, j, k;
  while (scanf("%d%d%d", &n, &m, &k) == 3) {
    cnt = 0;
    memset(pos, -1, sizeof(pos));
    for (i = 0; i < n; i++) {
      scanf("%s", s[i]);
      for (j = 0; j < m; j++) {
        if (s[i][j] == 'S') {
          u = i * m + j;
        } else if (s[i][j] == 'T') {
          v = i * m + j;
        } else {
          if (pos[s[i][j] - 'a'] == -1) {
            pos[s[i][j] - 'a'] = cnt++;
          }
        }
        s2[i * m + j] = s[i][j];
      }
    }
    mm = 0;
    for (i = 0; i <= k; i++) {
      dfs(cnt - 1, 0, i);
    }
    mind = -1;
    for (i = 0; i < mm; i++) {
      spfa(mask[i]);
    }
    if (mind == -1) {
      printf("-1\n");
    } else {
      puts(ans + 1);
    }
  }
  return 0;
}