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 n, m, q;
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
bool can[555];
bool vis[55][55];
char layout[55][55];
int dist[55][55];
int from[55][55];
int rnk[55][55];
char bst[2510];
vector<pair<int, int> > bpos[2510];
int sz[2510];
int sx, sy, tx, ty;
inline bool legal(int i, int j) { return i && j && (i <= n && j <= m); }
int res = 10000000;
string op;
void upd() {
  memset(dist, 0, sizeof(dist));
  memset(vis, 0, sizeof(vis));
  dist[tx][ty] = 1;
  queue<pair<int, int> > q;
  q.push(make_pair(tx, ty));
  while (!q.empty()) {
    int cx = q.front().first, cy = q.front().second;
    q.pop();
    for (int i = 3; ~i; --i) {
      int nx = cx + dx[i], ny = cy + dy[i];
      if (legal(nx, ny) && !dist[nx][ny] && can[layout[nx][ny]]) {
        dist[nx][ny] = dist[cx][cy] + 1;
        q.push(make_pair(nx, ny));
      }
    }
  }
  if (!dist[sx][sy] || dist[sx][sy] > res) return;
  string ans = "";
  bst[1] = ' ';
  bpos[1].clear();
  bpos[1].push_back(make_pair(sx, sy));
  sz[1] = 1;
  vis[sx][sy] = 1;
  for (int i = 1; i < dist[sx][sy] - 1; ++i) {
    bst[i + 1] = 'z';
    bpos[i + 1].clear();
    for (int j = sz[i] - 1; ~j; --j) {
      int nx = bpos[i][j].first, ny = bpos[i][j].second;
      for (int k = 3; ~k; --k) {
        int tx = nx + dx[k], ty = ny + dy[k];
        if (legal(tx, ty) && dist[tx][ty] == dist[nx][ny] - 1) {
          if (bst[i + 1] > layout[tx][ty]) bst[i + 1] = layout[tx][ty];
        }
      }
    }
    sz[i + 1] = 0;
    ans += bst[i + 1];
    for (int j = sz[i] - 1; ~j; --j) {
      int nx = bpos[i][j].first, ny = bpos[i][j].second;
      for (int k = 3; ~k; --k) {
        int tx = nx + dx[k], ty = ny + dy[k];
        if (legal(tx, ty) && !vis[tx][ty] && dist[tx][ty] == dist[nx][ny] - 1 &&
            bst[i + 1] == layout[tx][ty]) {
          bpos[i + 1].push_back(make_pair(tx, ty));
          vis[tx][ty] = 1;
          ++sz[i + 1];
        }
      }
    }
  }
  if (res > dist[sx][sy] || ans < op) {
    res = dist[sx][sy];
    op = ans;
  }
}
int main(void) {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; ++i) {
    scanf("%s", layout[i] + 1);
    for (int j = 1; j <= m; ++j) {
      if (layout[i][j] == 'S') {
        sx = i;
        sy = j;
      }
      if (layout[i][j] == 'T') {
        tx = i;
        ty = j;
      }
    }
  }
  can['S'] = 1;
  for (int i = 0; i < 26; ++i) {
    if (q == 1) {
      can[i + 'a'] = 1;
      upd();
      can[i + 'a'] = 0;
      continue;
    }
    for (int j = i + 1; j < 26; ++j) {
      if (q == 2) {
        can[i + 'a'] = 1;
        can[j + 'a'] = 1;
        upd();
        can[i + 'a'] = 0;
        can[j + 'a'] = 0;
        continue;
      }
      for (int k = j + 1; k < 26; ++k) {
        if (q == 3) {
          can[i + 'a'] = 1;
          can[j + 'a'] = 1;
          can[k + 'a'] = 1;
          upd();
          can[i + 'a'] = 0;
          can[j + 'a'] = 0;
          can[k + 'a'] = 0;
          continue;
        }
        for (int l = k + 1; l < 26; ++l) {
          can[i + 'a'] = 1;
          can[j + 'a'] = 1;
          can[k + 'a'] = 1;
          can[l + 'a'] = 1;
          upd();
          can[i + 'a'] = 0;
          can[j + 'a'] = 0;
          can[k + 'a'] = 0;
          can[l + 'a'] = 0;
        }
      }
    }
  }
  if (res > 1000000) {
    printf("-1");
    return 0;
  }
  printf("%s", op.c_str());
  return 0;
}