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;
struct data {
  int x, y, l, bnd;
  data(int a, int b, int c, int d) {
    x = a, y = b, l = c;
    bnd = d;
  }
  data(){};
};
int n, m, k, sx, sy, ex, ey;
bool use[30];
int ck[30];
int pos[55][55];
int d[55][55];
char a[55][55];
int xx[] = {1, 0, -1, 0};
int yy[] = {0, 1, 0, -1};
bool CK;
int S, E;
vector<pair<char, data> > v;
data from[55][55];
data q[5000];
string rst;
string go(int y, int x) {
  string bur;
  if (y == sy && x == sx) return "";
  if (a[y][x] != 'T') bur += a[y][x];
  return bur + go(from[y][x].y, from[y][x].x);
}
bool sf(pair<char, data> a, pair<char, data> b) { return a.first < b.first; }
int main() {
  scanf("%d%d%d", &n, &m, &k);
  int i, j;
  for (i = 1; i <= n; i++) scanf("%s", &a[i][1]);
  for (i = 1; i <= 4000; i++) rst += 'z';
  for (i = 0; i < k; i++) use[i] = 1;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++) {
      if (a[i][j] == 'S') sx = j, sy = i;
      if (a[i][j] == 'T') ex = j, ey = i;
    }
  while (1) {
    next_permutation(use, use + 27);
    if (use[0]) break;
    int cnt = 0;
    memset(ck, 0, sizeof(ck));
    for (i = 1; i <= 26; i++)
      if (use[i]) ck[i] = ++cnt;
    if (ck[1] == 1 && ck[2] == 2 && ck[3] == 3) {
      i = i;
    }
    for (i = 1; i <= n; i++)
      for (j = 1; j <= m; j++) pos[i][j] = ck[a[i][j] - 'a' + 1];
    pos[sy][sx] = pos[ey][ex] = 1;
    S = E = 1;
    memset(d, 0, sizeof(d));
    memset(q, 0, sizeof(q));
    q[S] = data(sx, sy, 1, 1);
    d[sy][sx] = 1;
    data K;
    while (S <= E) {
      int nE;
      K = q[S];
      if (K.x == ex && K.y == ey) {
        break;
      }
      for (nE = S; nE <= K.bnd; nE++) {
        int x = q[nE].x;
        int y = q[nE].y;
        if (q[nE].l == K.l && a[y][x] == a[K.y][K.x])
          continue;
        else
          break;
      }
      for (int j = S; j < nE; j++) {
        for (int i = 0; i < 4; i++) {
          int nx = q[j].x + xx[i];
          int ny = q[j].y + yy[i];
          if (d[ny][nx] || !pos[ny][nx]) continue;
          d[ny][nx] = q[j].l + 1;
          from[ny][nx] = q[j];
          v.push_back(make_pair(a[ny][nx], data(nx, ny, q[j].l + 1, 0)));
        }
      }
      sort(v.begin(), v.end(), sf);
      for (int i = 0; i < v.size(); i++) {
        q[++E] = v[i].second;
      }
      for (int i = 0; i < v.size(); i++) {
        q[E - i].bnd = E;
      }
      v.clear();
      S = nE;
    }
    if (d[ey][ex] == 0) continue;
    if (d[ey][ex] - 2 > rst.size()) continue;
    CK = 1;
    string bur = go(ey, ex);
    reverse(bur.begin(), bur.end());
    if (rst.size() < bur.size())
      continue;
    else if (rst.size() == bur.size())
      rst = min(rst, bur);
    else
      rst = bur;
  }
  if (CK == 0)
    printf("-1");
  else
    cout << rst;
  return 0;
}