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>
int IntMaxVal = (int)1e20;
int IntMinVal = (int)-1e20;
long long LongMaxVal = (long long)1e20;
long long LongMinVal = (long long)-1e20;
using namespace std;
template <typename T>
struct argument_type;
template <typename T, typename U>
struct argument_type<T(U)> {};
template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& s) {
  is >> s.first >> s.second;
  return is;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (int i = 0; i < v.size(); i++) os << v[i] << ' ';
  os << '\n';
  ;
  return os;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& s, pair<T1, T2>& t) {
  s << t.first << ' ' << t.second;
  return s;
}
template <typename T>
vector<T> readVector(int n) {
  vector<T> res(n);
  for (int i = 0; i < n; i++) cin >> res[i];
  return res;
}
vector<string> f;
int n, m;
int sx, sy;
int ex, ey;
int wayLen[50][50];
bool visited[50][50];
class wayNode {
 public:
  vector<pair<char, char> > positions;
  int cameFrom;
  char cameBy;
};
vector<wayNode> q(2501);
inline void tryQueue(int destIndex, int y, int x, char c) {
  if (y < 0 || x < 0 || y == n || x == m || (f[y][x] != c && f[y][x] != 'T') ||
      visited[y][x])
    return;
  q[destIndex].positions.push_back(make_pair((char)y, (char)x));
  visited[y][x] = true;
}
inline void tryQueue(int curIndex, int& destIndex, char c) {
  for (auto& pos : q[curIndex].positions) {
    tryQueue(destIndex, pos.first - 1, pos.second, c);
    tryQueue(destIndex, pos.first + 1, pos.second, c);
    tryQueue(destIndex, pos.first, pos.second - 1, c);
    tryQueue(destIndex, pos.first, pos.second + 1, c);
  }
  if (q[destIndex].positions.size()) {
    q[destIndex].cameBy = c;
    q[destIndex].cameFrom = curIndex;
    destIndex++;
    q[destIndex].positions.clear();
  }
}
vector<char> path;
string getAns(char c1, char c2, char c3, char c4) {
  for (int y = 0; y < n; ++y)
    for (int x = 0; x < m; ++x) wayLen[y][x] = -1;
  for (int y = 0; y < n; ++y)
    for (int x = 0; x < m; ++x) visited[y][x] = false;
  int nextP = 0;
  q[nextP].positions.clear();
  q[nextP].positions.push_back(make_pair(sy, sx));
  q[nextP].cameFrom = -1;
  visited[sy][sx] = true;
  nextP++;
  q[nextP].positions.clear();
  if (c2 < c1) swap(c1, c2);
  if (c3 < c2) swap(c2, c3);
  if (c4 < c3) swap(c3, c4);
  for (int i = 0; i < q.size(); ++i) {
    for (auto& p : q[i].positions)
      if (p.first == ey && p.second == ex) {
        path.clear();
        int pointer = i;
        pointer = q[pointer].cameFrom;
        while (pointer) {
          path.push_back(q[pointer].cameBy);
          pointer = q[pointer].cameFrom;
        }
        string res = "";
        for (int j = path.size() - 1; j >= 0; --j) res.push_back(path[j]);
        for (int j = 0; j < nextP; ++j)
          vector<pair<char, char> >().swap(q[j].positions);
        return res;
      }
    if (c1 != '-') tryQueue(i, nextP, c1);
    if (c2 != '-') tryQueue(i, nextP, c2);
    if (c3 != '-') tryQueue(i, nextP, c3);
    if (c4 != '-') tryQueue(i, nextP, c4);
  }
  for (int j = 0; j < nextP; ++j)
    vector<pair<char, char> >().swap(q[j].positions);
  return "|";
}
int main() {
  srand(time(NULL));
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  int k;
  cin >> k;
  ;
  f = readVector<string>(n);
  for (int y = 0; y < n; ++y)
    for (int x = 0; x < m; ++x)
      if (f[y][x] == 'S') {
        sx = x;
        sy = y;
      }
  for (int y = 0; y < n; ++y)
    for (int x = 0; x < m; ++x)
      if (f[y][x] == 'T') {
        ex = x;
        ey = y;
      }
  vector<char> starts;
  if (sx > 0) starts.push_back(f[sy][sx - 1]);
  if (sx < m - 1) starts.push_back(f[sy][sx + 1]);
  if (sy > 0) starts.push_back(f[sy - 1][sx]);
  if (sy < n - 1) starts.push_back(f[sy + 1][sx]);
  starts.push_back('a');
  sort(starts.begin(), starts.end());
  starts.resize(unique(starts.begin(), starts.end()) - starts.begin());
  string ans = "|";
  bool hasAns = false;
  for (auto c1 : starts)
    if (c1 != 'T') {
      for (char c2 = 'a'; c2 <= 'z'; c2++)
        for (char c3 = c2 + 1; c3 <= 'z'; c3++)
          for (char c4 = c3 + 1; c4 <= 'z'; c4++) {
            if (c1 == c2 || c1 == c3 || c1 == c4) continue;
            string s = getAns(c1, k > 1 ? c2 : '-', k > 2 ? c3 : '-',
                              k > 3 ? c4 : '-');
            if (s[0] == '|') continue;
            if (!hasAns || s.length() < ans.length() ||
                (s.length() == ans.length() && s < ans))
              ans = s, hasAns = true;
          }
    }
  if (!hasAns) {
    cout << -1;
  } else {
    cout << ans;
  }
}