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;
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  os << "{" << p.first << ", " << p.second << "}";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& p) {
  os << "[";
  int i = 0;
  for (typename vector<T>::const_iterator it = p.begin(); it != p.end(); ++it) {
    os << (i == 0 ? "" : ", ") << *it;
    i++;
  }
  os << "]";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& p) {
  os << "[";
  int i = 0;
  for (typename set<T>::const_iterator it = p.begin(); it != p.end(); ++it) {
    os << (i == 0 ? "" : ", ") << *it;
    i++;
  }
  os << "]";
  return os;
}
template <class K, class V>
ostream& operator<<(ostream& os, const map<K, V>& p) {
  os << "[";
  int i = 0;
  for (typename map<K, V>::const_iterator it = p.begin(); it != p.end(); ++it) {
    os << (i == 0 ? "" : ", ") << *it;
    i++;
  }
  os << "]";
  return os;
}
template <class T>
string toString(const T& o) {
  stringstream ss;
  ss << o;
  string ret;
  getline(ss, ret);
  return ret;
}
template <class T>
vector<T> subv(const vector<T>& v, int from, int to) {
  return vector<T>(v.begin() + min(max(0, from), (int)v.size()),
                   v.begin() + min(max(0, to), (int)v.size()));
}
pair<int, int> operator+(const pair<int, int>& a, const pair<int, int>& b) {
  return make_pair(a.first + b.first, a.second + b.second);
}
pair<int, int> operator*(const int& a, const pair<int, int>& b) {
  return make_pair(a * b.first, a * b.second);
}
vector<vector<int> > a;
int si, sj, ti, tj;
int f[64][64];
int n, m;
int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int c1, c2, c3, c4;
void go() {
  queue<pair<int, int> > q;
  queue<int> st;
  q.push(make_pair(si, sj));
  st.push(1);
  while (q.size()) {
    pair<int, int> p = q.front();
    q.pop();
    int step = st.front();
    st.pop();
    if (f[p.first][p.second] != 0) continue;
    f[p.first][p.second] = step;
    step++;
    for (int k = 0; k < 4; ++k) {
      int x = p.first + d[k][0];
      int y = p.second + d[k][1];
      if (0 <= x && x < n && 0 <= y && y < m) {
        int& v = a[x][y];
        bool ok = (v == c1 || v == c2 || v == c3 || v == c4);
        if (v < 0 || ok)
          if (f[x][y] == 0) {
            q.push(make_pair(x, y));
            st.push(step);
          }
      }
    }
  }
}
int best_len = -1;
string best_path = "";
string short_path = "";
vector<vector<string> > paths;
string path(int x, int y) {
  string& ret = paths[x][y];
  if (ret != "") return ret;
  if (x == ti && y == tj) {
    ret = "T";
    return ret;
  }
  int fd = f[x][y];
  string tmp = "";
  for (int k = 0; k < 4; ++k) {
    int xx = x + d[k][0];
    int yy = y + d[k][1];
    if (0 <= xx && xx < n && 0 <= yy && yy < m && f[xx][yy] == f[x][y] + 1) {
      string r = path(xx, yy);
      if (r != "X" && (tmp == "" || r < tmp)) tmp = r;
    }
  }
  if (tmp == "")
    ret = "X";
  else {
    char c = ((x == si && y == sj) ? 'S' : (a[x][y] + 'a'));
    ret = c + tmp;
  }
  return ret;
}
vector<int> ch;
vector<vector<int> > comb;
vector<string> scomb;
void combination(int pos, int len, vector<int> v) {
  if (len == 0) comb.push_back(v);
  if (len == 0 || len > pos + 1) return;
  combination(pos - 1, len, v);
  v.push_back(ch[pos]);
  combination(pos - 1, len - 1, v);
}
int main() {
  int k;
  cin >> n >> m >> k;
  if (n * m == 2) {
    cout << endl;
    return 0;
  }
  a = vector<vector<int> >(n, vector<int>(m, 0));
  paths.resize(n, vector<string>(m, ""));
  vector<vector<string> > old = paths;
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    for (int j = 0; j < m; ++j) {
      if (s[j] == 'S') {
        si = i;
        sj = j;
        a[i][j] = -1;
      } else if (s[j] == 'T') {
        ti = i;
        tj = j;
        a[i][j] = -2;
      } else {
        a[i][j] = s[j] - 'a';
        ch.push_back(a[i][j]);
      }
    }
  }
  sort(ch.begin(), ch.end());
  ch.resize(unique(ch.begin(), ch.end()) - ch.begin());
  k = min(k, (int)ch.size());
  combination(ch.size() - 1, k, vector<int>());
  for (int i = 0; i < comb.size(); ++i) {
    string s = "";
    for (int j = 0; j < comb[i].size(); ++j) s += (comb[i][j] + 'a');
    sort(s.begin(), s.end());
    scomb.push_back(s);
  }
  vector<int> pw(26, 0);
  for (int i = 0; i < 26; ++i) pw[i] = (1 << i);
  for (int i = 0; i < comb.size(); ++i) {
    c1 = c2 = c3 = c4 = -100;
    int sz = comb[i].size();
    c1 = comb[i][0];
    if (sz > 1) c2 = comb[i][1];
    if (sz > 2) c3 = comb[i][2];
    if (sz > 3) c4 = comb[i][3];
    memset(f, 0, sizeof(f));
    go();
    if (f[ti][tj] == 0) continue;
    if (best_len != -1 && f[ti][tj] > best_len) continue;
    if (f[ti][tj] == best_len)
      if (*short_path.rbegin() <= scomb[i][0]) continue;
    paths = old;
    path(si, sj);
    string& cand = paths[si][sj];
    if ((best_len == -1 || cand.size() < best_len) ||
        (cand.size() == best_len && cand < best_path)) {
      best_len = cand.size();
      best_path = cand;
      cand = string(cand.begin() + 1, cand.end() - 1);
      sort(cand.begin(), cand.end());
      cand.resize(unique(cand.begin(), cand.end()) - cand.begin());
      short_path = cand;
    }
  }
  if (best_len == -1)
    cout << -1 << endl;
  else {
    string& s = best_path;
    cout << string(s.begin() + 1, s.end() - 1) << endl;
  }
  return 0;
}