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;
char _;
const int maxN = 50 + 5;
const int mod = 1000 * 1000 * 1000 + 7;
const int base = 701;
const int SQ = 330;
const int maxL = 302;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
char a[maxN][maxN];
int sx, sy, tx, ty;
int mark[26], cnt;
string res;
int n, m, k;
int dis[maxN][maxN];
pair<int, int> q[2500];
bool is_ok(int x, int y) {
  if (x < 0 || y < 0 || n <= x || m <= y) return false;
  return true;
}
pair<int, int> par[maxN][maxN];
int proi[maxN][maxN];
bool cmp(const pair<int, int> &p, const pair<int, int> &q) {
  if (a[p.first][p.second] != a[q.first][q.second])
    return (a[p.first][p.second] < a[q.first][q.second]);
  pair<int, int> pp = par[p.first][p.second], qq = par[q.first][q.second];
  return (proi[pp.first][pp.second] < proi[qq.first][qq.second]);
}
string ss;
void solve(int x, int y) {
  if (x == tx && y == ty) return;
  if (x != sx || y != sy) ss += a[x][y];
  solve(par[x][y].first, par[x][y].second);
}
void check() {
  memset(dis, 0, sizeof dis);
  memset(proi, 0, sizeof proi);
  memset(par, -1, sizeof par);
  dis[tx][ty] = 1;
  int st = 0, en = 0;
  q[en++] = {tx, ty};
  while (st < en) {
    if (st && dis[q[st].first][q[st].second] >
                  dis[q[st - 1].first][q[st - 1].second]) {
      sort(q + st, q + en, cmp);
      int cnt = 0;
      for (int i = st + 1; i < en; i++) {
        if (cmp(q[i - 1], q[i])) cnt++;
        proi[q[i].first][q[i].second] = cnt;
      }
    }
    int x = q[st].first, y = q[st].second;
    st++;
    if (make_pair(x, y) == make_pair(sx, sy)) break;
    for (int i = 0; i < 4; i++) {
      int v = x + dx[i], u = y + dy[i];
      if (is_ok(v, u) && dis[v][u] == 0 &&
          (a[v][u] == 'S' || mark[a[v][u] - 'a'] == 1)) {
        dis[v][u] = dis[x][y] + 1;
        q[en++] = {v, u};
        par[v][u] = {x, y};
      }
    }
  }
  if (dis[sx][sy] == 0) return;
  if (dis[sx][sy] - 2 > (int)res.size()) return;
  ss = "";
  solve(sx, sy);
  if (dis[sx][sy] - 2 < (int)res.size())
    res = ss;
  else
    res = min(res, ss);
}
void bt(int t) {
  if (t == 26) return;
  if (cnt < k) {
    mark[t] = 1;
    cnt++;
    check();
    bt(t + 1);
    mark[t] = 0;
    cnt--;
  }
  bt(t + 1);
}
int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
      if (a[i][j] == 'S') sx = i, sy = j;
      if (a[i][j] == 'T') tx = i, ty = j;
    }
  res = string(3000, 'z');
  bt(0);
  if (res.size() == 3000) {
    cout << -1 << endl;
    return 0;
  }
  cout << res << endl;
  return 0;
}