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 A[53][53];
int q[(4 * 15000)];
int dist[53][53];
int dr[] = {-1, 0, 0, 1};
int dc[] = {0, -1, 1, 0};
int sz(int s) {
  int ans = 0;
  while (s) ans += s & 1, s >>= 1;
  return ans;
}
int N, M, K;
bool marked[53][53];
void mark(int i, int j) {
  if (marked[i][j]) return;
  marked[i][j] = true;
  for (int mv = 0; mv < (4); ++mv) {
    int i2 = i + dr[mv];
    int j2 = j + dc[mv];
    if (i2 < 0 || i2 >= N) continue;
    if (j2 < 0 || j2 >= M) continue;
    if (marked[i2][j2]) continue;
    if (dist[i2][j2] < 0) continue;
    if (dist[i2][j2] == dist[i][j] - 1) mark(i2, j2);
  }
}
int main() {
  cin >> N >> M >> K;
  for (int i = 0; i < (N); ++i) scanf("%s", A[i]);
  int seen = 0;
  int ti = -1, tj = -1;
  int si = -1, sj = -1;
  for (int i = 0; i < (N); ++i)
    for (int j = 0; j < (M); ++j)
      if (A[i][j] == 'T')
        ti = i, tj = j;
      else if (A[i][j] == 'S')
        si = i, sj = j;
      else
        seen |= 1 << (A[i][j] - 'a');
  assert(si >= 0 && sj >= 0);
  assert(ti >= 0 && tj >= 0);
  int h = 0, t = -1;
  int S = 1 << 26;
  for (int s = 0; s < (S); ++s) {
    if ((s | seen) > seen) continue;
    if (sz(s) > K) continue;
    q[++t] = s;
    assert(t < (4 * 15000));
  }
  string ans(N * M + 1, 'z');
  while (h <= t) {
    int s = q[h++];
    queue<int> Q;
    Q.push(((si)*50 + (sj)));
    memset(dist, -1, sizeof(dist));
    dist[si][sj] = 0;
    while (!Q.empty()) {
      int n = Q.front();
      Q.pop();
      int i = ((n) / 50), j = ((n) % 50);
      if (i == ti && j == tj) break;
      assert(dist[i][j] >= 0);
      for (int mv = 0; mv < (4); ++mv) {
        int i2 = i + dr[mv];
        int j2 = j + dc[mv];
        if (i2 < 0 || i2 >= N) continue;
        if (j2 < 0 || j2 >= M) continue;
        if (A[i2][j2] != 'T' && !(s & (1 << (A[i2][j2] - 'a')))) continue;
        if (dist[i2][j2] < 0 || dist[i][j] + 1 < dist[i2][j2]) {
          dist[i2][j2] = dist[i][j] + 1;
          Q.push(((i2)*50 + (j2)));
        }
      }
    }
    if (dist[ti][tj] < 0 || dist[ti][tj] > (int)ans.size() + 1) continue;
    memset(marked, 0, sizeof(marked));
    mark(ti, tj);
    vector<int> now;
    vector<int> next;
    string path;
    char nextc;
    now.push_back(((si)*50 + (sj)));
    while (!now.empty()) {
      next.clear();
      nextc = 'z' + 1;
      int m = now.size();
      for (int x = 0; x < (m); ++x) {
        int n = now[x];
        int i = ((n) / 50), j = ((n) % 50);
        for (int mv = 0; mv < (4); ++mv) {
          int i2 = i + dr[mv];
          int j2 = j + dc[mv];
          if (i2 < 0 || i2 >= N) continue;
          if (j2 < 0 || j2 >= M) continue;
          if (!marked[i2][j2]) continue;
          if (dist[i2][j2] != dist[i][j] + 1) continue;
          char c = A[i2][j2];
          if (c < nextc) nextc = c;
        }
      }
      for (int x = 0; x < (m); ++x) {
        int n = now[x];
        int i = ((n) / 50), j = ((n) % 50);
        for (int mv = 0; mv < (4); ++mv) {
          int i2 = i + dr[mv];
          int j2 = j + dc[mv];
          if (i2 < 0 || i2 >= N) continue;
          if (j2 < 0 || j2 >= M) continue;
          if (!marked[i2][j2]) continue;
          if (dist[i2][j2] != dist[i][j] + 1) continue;
          char c = A[i2][j2];
          if (c != nextc) continue;
          next.push_back(((i2)*50 + (j2)));
        }
      }
      sort(next.begin(), next.end());
      next.erase(unique(next.begin(), next.end()), next.end());
      swap(now, next);
      if (!now.empty()) path += nextc;
    }
    assert((int)path.length() == dist[ti][tj] && dist[ti][tj] >= 1);
    path = path.substr(0, dist[ti][tj] - 1);
    if (path.length() < ans.length() ||
        (path.length() == ans.length() && path < ans)) {
      ans = path;
    }
  }
  if ((int)ans.length() <= N * M)
    cout << ans << endl;
  else
    cout << -1 << endl;
}