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;
const int P = 1e9 + 7;
int add(int a, int b) {
  if ((a += b) >= P) a -= P;
  return a;
}
int sub(int a, int b) {
  if ((a -= b) < 0) a += P;
  return a;
}
int mul(int a, int b) { return 1ll * a * b % P; }
int kpow(int a, int b) {
  int r = 1;
  for (; b; b >>= 1, a = mul(a, a)) {
    if (b & 1) r = mul(r, a);
  }
  return r;
}
const int N = 51;
int ans2, n, m, k, use[1000], d[N][N];
string ans, a[N], ss[N][N];
queue<pair<int, int> > q;
pair<int, int> s, t;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
void solve() {
  memset(d, 0, sizeof(d));
  q.push(s);
  d[s.first][s.second] = 1;
  ss[t.first][t.second] = "S";
  while (!q.empty()) {
    auto tmp = q.front();
    q.pop();
    int x = tmp.first, y = tmp.second;
    for (int i = (0); i < (4); i++) {
      int xx = x + dx[i], yy = y + dy[i];
      if (xx > n || xx < 1 || yy > m || yy < 1 || !use[a[xx][yy]]) continue;
      if (xx == t.first && yy == t.second) {
        if (!d[xx][yy]) d[xx][yy] = d[x][y] + 1;
        if (d[xx][yy] != d[x][y] + 1) continue;
        if (ss[xx][yy] == "S")
          ss[xx][yy] = ss[x][y];
        else
          ss[xx][yy] = min(ss[xx][yy], ss[x][y]);
        continue;
      }
      if (!d[xx][yy]) {
        d[xx][yy] = d[x][y] + 1;
        ss[xx][yy] = ss[x][y] + a[xx][yy];
        q.push(make_pair(xx, yy));
      } else if (d[xx][yy] == d[x][y] + 1)
        ss[xx][yy] = min(ss[x][y] + a[xx][yy], ss[xx][yy]);
    }
  }
  if (d[t.first][t.second] == 0) return;
  if (d[t.first][t.second] < ans2) {
    ans2 = d[t.first][t.second];
    ans = ss[t.first][t.second];
  }
  if (d[t.first][t.second] > ans2) return;
  ans = min(ans, ss[t.first][t.second]);
}
void dfs(int d, int now) {
  if (d == k + 1) {
    solve();
    return;
  }
  for (int i = (now); i < ('z' + 1); i++) {
    use[i] = 1;
    dfs(d + 1, i + 1);
    use[i] = 0;
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  cin >> n >> m >> k;
  for (int i = (1); i < (n + 1); i++) cin >> a[i], a[i] = " " + a[i];
  for (int i = (1); i < (n + 1); i++)
    for (int j = (1); j < (m + 1); j++)
      if (a[i][j] == 'S')
        s = make_pair(i, j);
      else if (a[i][j] == 'T')
        t = make_pair(i, j);
  use['T'] = 1;
  ans2 = (1ll << (30));
  ans = "S";
  dfs(1, 'a');
  if (ans == "S")
    cout << -1;
  else
    cout << ans;
  return 0;
}