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 F, class T>
T convert(F a, int p = -1) {
  stringstream ss;
  if (p >= 0) ss << fixed << setprecision(p);
  ss << a;
  T r;
  ss >> r;
  return r;
}
template <class T>
void db(T a, int p = -1) {
  if (p >= 0) cout << fixed << setprecision(p);
  cout << a << " ";
}
template <class T>
T gcd(T a, T b) {
  T r;
  while (b != 0) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
template <class T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
template <class T>
T sqr(T x) {
  return x * x;
}
template <class T>
T cube(T x) {
  return x * x * x;
}
template <class T>
struct Triple {
  T x, y, z;
  Triple() {}
  Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {}
};
template <class T>
Triple<T> euclid(T a, T b) {
  if (b == 0) return Triple<T>(1, 0, a);
  Triple<T> r = euclid(b, a % b);
  return Triple<T>(r.y, r.x - a / b * r.y, r.z);
}
template <class T>
int getbit(T s, int i) {
  return (s >> i) & 1;
}
template <class T>
T onbit(T s, int i) {
  return s | (T(1) << i);
}
template <class T>
T offbit(T s, int i) {
  return s & (~(T(1) << i));
}
template <class T>
int cntbit(T s) {
  return s == 0 ? 0 : cntbit(s >> 1) + (s & 1);
}
const int bfsz = 1 << 16;
char bf[bfsz + 5];
int rsz = 0;
int ptr = 0;
char gc() {
  if (rsz <= 0) {
    ptr = 0;
    rsz = fread(bf, 1, bfsz, stdin);
    if (rsz <= 0) return EOF;
  }
  --rsz;
  return bf[ptr++];
}
void ga(char &c) {
  c = EOF;
  while (!isalpha(c)) c = gc();
}
int gs(char s[]) {
  int l = 0;
  char c = gc();
  while (isspace(c)) c = gc();
  while (c != EOF && !isspace(c)) {
    s[l++] = c;
    c = gc();
  }
  s[l] = '\0';
  return l;
}
template <class T>
bool gi(T &v) {
  v = 0;
  char c = gc();
  while (c != EOF && c != '-' && !isdigit(c)) c = gc();
  if (c == EOF) return false;
  bool neg = c == '-';
  if (neg) c = gc();
  while (isdigit(c)) {
    v = v * 10 + c - '0';
    c = gc();
  }
  if (neg) v = -v;
  return true;
}
const double PI = 2 * acos(0);
const string months[] = {"January",   "February", "March",    "April",
                         "May",       "June",     "July",     "August",
                         "September", "October",  "November", "December"};
const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dr[] = {-1, 0, +1, 0};
const int dc[] = {0, +1, 0, -1};
const int inf = (int)1e9 + 5;
const long long linf = (long long)1e16 + 5;
const double eps = 1e-9;
const long long mod = 100000007;
int n, m, k;
int a[5];
string kq, s[55];
int lenkq = inf, rs, cs, rf, cf;
pair<int, int> back[55][55];
bool cmp(pair<int, int> const &A, pair<int, int> const &B) {
  return s[A.first][A.second] < s[B.first][B.second];
}
bool thoaman(int r, int c) {
  if (r >= 0 && r < n && c >= 0 && c < m) {
    if (s[r][c] == 'T') return true;
    for (typeof(k) i = 0; i < (k); ++i)
      if (a[i] == s[r][c] - 'a') return true;
    return false;
  }
  return false;
}
string reverse(string x) {
  string res = "";
  for (int i = x.length() - 1; i >= 0; i--) res.push_back(x[i]);
  return res;
}
void cal() {
  int f[55][55], r, c, rr, cc;
  memset(f, -1, sizeof(f));
  f[rs][cs] = 0;
  vector<pair<int, int> > que[55 * 55];
  pair<int, int> temp[55 * 55];
  int num;
  int size = 0;
  que[size++].push_back(make_pair(rs, cs));
  for (typeof(size) i = 0; i < (size); ++i) {
    num = 0;
    for (typeof(((int)(que[i]).size())) j = 0; j < (((int)(que[i]).size()));
         ++j) {
      r = que[i][j].first;
      c = que[i][j].second;
      for (typeof(4) t = 0; t < (4); ++t) {
        rr = r + dr[t];
        cc = c + dc[t];
        if (thoaman(rr, cc)) {
          if (f[rr][cc] == -1) {
            f[rr][cc] = f[r][c] + 1;
            back[rr][cc] = make_pair(r, c);
            temp[num++] = make_pair(rr, cc);
          }
        }
      }
    }
    sort(temp, temp + num, cmp);
    que[size].push_back(temp[0]);
    for (typeof(num - 1) j = (1); j <= (num - 1); ++j) {
      if (cmp(temp[j - 1], temp[j])) {
        size++;
        que[size].push_back(temp[j]);
      } else
        que[size].push_back(temp[j]);
    }
    if (num > 0) size++;
  }
  if (f[rf][cf] == -1) return;
  r = back[rf][cf].first;
  c = back[rf][cf].second;
  string res = "";
  while (r != rs || c != cs) {
    res.push_back(s[r][c]);
    rr = back[r][c].first;
    cc = back[r][c].second;
    r = rr;
    c = cc;
  }
  res = reverse(res);
  if (res.length() < lenkq || (res.length() == lenkq && res.compare(kq) < 0)) {
    kq = res;
    lenkq = res.length();
  }
}
void go(int id, int x) {
  if (id == k) {
    cal();
    return;
  }
  for (typeof(25) i = (x); i <= (25); ++i) {
    a[id] = i;
    go(id + 1, i + 1);
  }
}
int main() {
  cin >> n >> m >> k;
  for (typeof(n) i = 0; i < (n); ++i) {
    cin >> s[i];
    for (typeof(m) j = 0; j < (m); ++j) {
      if (s[i][j] == 'S') {
        rs = i;
        cs = j;
      }
      if (s[i][j] == 'T') {
        rf = i;
        cf = j;
      }
    }
  }
  go(0, 0);
  if (lenkq >= inf) {
    printf("-1");
    return 0;
  }
  cout << kq;
}