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 LIM = 50;
const int MAX_BIT = 26;
const int MAX_MASK = 1 << MAX_BIT;
struct state {
  char s;
  int i, j, pi, pj;
  state() {}
  state(char s, int i, int j, int pi, int pj)
      : s(s), i(i), j(j), pi(pi), pj(pj) {}
};
bool operator<(const state& a, const state& b) { return a.s > b.s; }
string f[LIM], ans = "";
int used = 0;
int us[LIM][LIM];
pair<int, int> p[LIM][LIM];
int n, m, k;
int si, sj, fi, fj;
vector<pair<int, int>> edges[LIM][LIM];
int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};
bool bit(const int mask, const int b) { return (mask >> b) & 1; }
int cnt_bits(const int mask) {
  int res = 0;
  for (int i = 0; i < MAX_BIT; ++i) res += bit(mask, i);
  return res;
}
void get_next(int& mask, const int k) {
  if (cnt_bits(mask) < k) {
    ++mask;
  } else {
    for (int i = 0; i < MAX_BIT; ++i)
      if (bit(mask, i)) {
        mask += (1 << i);
        return;
      }
  }
}
void init_edges() {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
      for (int id = 0; id < 4; ++id)
        if (i + di[id] >= 0 && i + di[id] < n && j + dj[id] >= 0 &&
            j + dj[id] < m && f[i + di[id]][j + dj[id]] == 'T')
          edges[i][j].push_back(make_pair(i + di[id], j + dj[id]));
      for (char c = 'a'; c <= 'z'; ++c)
        for (int id = 0; id < 4; ++id)
          if (i + di[id] >= 0 && i + di[id] < n && j + dj[id] >= 0 &&
              j + dj[id] < m && f[i + di[id]][j + dj[id]] == c)
            edges[i][j].push_back(make_pair(i + di[id], j + dj[id]));
    }
}
void show(int mask) {
  for (int i = 0; i < MAX_BIT; ++i)
    if (bit(mask, i)) cout << (char)('a' + i);
  cout << endl;
}
string get_res(int i, int j) {
  string res = "";
  while (i != -1) {
    res += f[i][j];
    int ni = p[i][j].first;
    j = p[i][j].second;
    i = ni;
  }
  reverse(res.begin(), res.end());
  return res;
}
string bfs(int mask) {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
      us[i][j] = -1;
    }
  int num = 1;
  p[si][sj] = make_pair(-1, -1);
  us[si][sj] = num;
  queue<pair<int, int>> q;
  q.push(make_pair(si, sj));
  priority_queue<state> pq;
  while (!q.empty()) {
    ++num;
    int i = q.front().first, j = q.front().second;
    while (!q.empty() && us[i][j] == us[q.front().first][q.front().second]) {
      i = q.front().first;
      j = q.front().second;
      for (int id = 0; id < (int)edges[i][j].size(); ++id) {
        int ni = edges[i][j][id].first, nj = edges[i][j][id].second;
        pq.push(state(f[ni][nj], ni, nj, i, j));
      }
      q.pop();
    }
    char last = pq.top().s;
    while (!pq.empty()) {
      int ni = pq.top().i, nj = pq.top().j;
      if (pq.top().s != last) {
        ++num;
        last = pq.top().s;
      }
      if ((f[ni][nj] == 'T' || bit(mask, f[ni][nj] - 'a')) &&
          us[ni][nj] == -1) {
        p[ni][nj] = make_pair(pq.top().pi, pq.top().pj);
        us[ni][nj] = num;
        q.push(make_pair(ni, nj));
      }
      pq.pop();
    }
    if (us[fi][fj] != -1) break;
  }
  if (us[fi][fj] == -1) return "";
  return get_res(fi, fj);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m >> k;
  for (int i = 0; i < n; ++i) cin >> f[i];
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
      used |= (1 << (f[i][j] - 'a'));
      if (f[i][j] == 'S') {
        si = i;
        sj = j;
      }
      if (f[i][j] == 'T') {
        fi = i;
        fj = j;
      }
    }
  init_edges();
  int mask = 0;
  while (mask < MAX_MASK) {
    get_next(mask, k);
    string tans = bfs(mask);
    if (tans != "") {
      if (ans == "") {
        ans = tans;
      } else {
        if (ans.length() > tans.length())
          ans = tans;
        else if (ans.length() == tans.length())
          ans = min(ans, tans);
      }
    }
  }
  if (ans == "") {
    cout << -1;
  } else {
    for (int i = 1; i + 1 < (int)ans.length(); ++i) cout << ans[i];
  }
  return 0;
}