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 table[51][51];
int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[] = {0, -1, 0, 1, 1, -1, -1, 1};
int mem[50][50][17903];
struct State {
  int r, c;
  int vis;
  int& ref() { return mem[r][c][vis]; }
};
int stateToMask[18000];
int main(int argc, char* argv[]) {
  int N;
  cin >> N;
  int M;
  cin >> M;
  int K;
  cin >> K;
  int cnt = 0;
  set<int> m;
  for (int a = 0; a <= 'z' - 'a'; a++) {
    for (int b = 0; b <= a; b++) {
      for (int c = 0; c <= b; c++) {
        for (int d = 0; d <= c; d++) {
          int mask = (1 << a) | (1 << b) | (1 << c) | (1 << d);
          int bcnt = 1;
          if (b != a) bcnt++;
          if (c != a && c != b) bcnt++;
          if (d != c && d != a && d != b) bcnt++;
          if (bcnt != K) continue;
          if (m.find(mask) != m.end()) continue;
          m.insert(mask);
          stateToMask[cnt] = mask;
          cnt++;
        }
      }
    }
  }
  for (int i = 0; i < N; i++) scanf("%s", table[i]);
  memset(mem, -1, sizeof(mem));
  State s;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      if (table[i][j] == 'T') {
        s.c = j;
        s.r = i;
      }
    }
  }
  queue<State> q;
  for (int mask = 0; mask < cnt; mask++) {
    s.vis = mask;
    s.ref() = 0;
    q.push(s);
  }
  while (!q.empty()) {
    State s = q.front();
    q.pop();
    int len = s.ref();
    int mask = stateToMask[s.vis];
    for (int k = 0; k < 4; k++) {
      State ns;
      ns.c = s.c + dx[k];
      ns.r = s.r + dy[k];
      ns.vis = s.vis;
      if (ns.c < 0 || ns.c >= M) continue;
      if (ns.r < 0 || ns.r >= N) continue;
      if (table[ns.r][ns.c] != 'S' && table[ns.r][ns.c] != 'T') {
        if ((mask & (1 << (table[ns.r][ns.c] - 'a'))) == 0) continue;
      }
      if (ns.ref() == -1) {
        ns.ref() = len + 1;
        q.push(ns);
      }
    }
  }
  int len = 1000000;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      if (table[i][j] == 'S') {
        s.c = j;
        s.r = i;
      }
    }
  }
  for (int i = 0; i < cnt; i++) {
    if (mem[s.r][s.c][i] != -1) {
      len = min(len, mem[s.r][s.c][i]);
    }
  }
  if (len == 1000000) {
    printf("-1\n");
    return 0;
  }
  vector<State> qq;
  string ans;
  for (int vis = 0; vis < cnt; vis++) {
    s.vis = vis;
    if (mem[s.r][s.c][vis] == len) qq.push_back(s);
  }
  for (int i = 0; i < len - 1; i++) {
    char next = 'z' + 1;
    for (int j = 0; j < qq.size(); j++) {
      State s = qq[j];
      int mask = stateToMask[s.vis];
      for (int k = 0; k < 4; k++) {
        State ns;
        ns.c = s.c + dx[k];
        ns.r = s.r + dy[k];
        ns.vis = s.vis;
        if (ns.c < 0 || ns.c >= M) continue;
        if (ns.r < 0 || ns.r >= N) continue;
        if (table[ns.r][ns.c] != 'S' && table[ns.r][ns.c] != 'T')
          if (((mask & (1 << (table[ns.r][ns.c] - 'a')))) == 0) continue;
        if (ns.ref() + i == len - 1) {
          next = min(next, table[ns.r][ns.c]);
        }
      }
    }
    ans += next;
    vector<State> nq;
    for (int j = 0; j < qq.size(); j++) {
      State s = qq[j];
      int mask = stateToMask[s.vis];
      for (int k = 0; k < 4; k++) {
        State ns;
        ns.c = s.c + dx[k];
        ns.r = s.r + dy[k];
        ns.vis = s.vis;
        if (ns.c < 0 || ns.c >= M) continue;
        if (ns.r < 0 || ns.r >= N) continue;
        if (table[ns.r][ns.c] != 'S' && table[ns.r][ns.c] != 'T')
          if (((mask & (1 << (table[ns.r][ns.c] - 'a')))) == 0) continue;
        if (next == table[ns.r][ns.c] && ns.ref() + i == len - 1) {
          nq.push_back(ns);
          ns.ref() = -2;
        }
      }
    }
    nq.swap(qq);
  }
  printf("%s\n", ans.c_str());
  return 0;
}