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;
const long double EPS = 1E-9;
const int INF = (int)1E9;
const long long INF64 = (long long)1E18;
const long double PI = 2 * acos(.0);
char mapa[55][55];
int resp[55][55];
bool dk[55][55];
pair<int, int> path[55][55];
int n, m, kk;
int mx[4] = {0, 0, 1, -1};
int my[4] = {1, -1, 0, 0};
int xini, yini, xfin, yfin;
int checkmask = -1;
string recover(int x, int y) {
  if (x == xini && y == yini) return "";
  if (mapa[x][y] == 'S') return recover(path[x][y].first, path[x][y].second);
  return mapa[x][y] + recover(path[x][y].first, path[x][y].second);
}
string bfs() {
  string result = ">";
  int len = INF;
  for (int i = 0; i < 26; i++) {
    for (int j = i; j < 26; j++) {
      for (int k = j; k < 26; k++) {
        for (int l = k; l < 26; l++) {
          int mask = 0;
          mask |= (1 << l);
          if (kk > 1) mask |= (1 << k);
          if (kk > 2) mask |= (1 << j);
          if (kk > 3) mask |= (1 << i);
          if (__builtin_popcount(mask) != kk) continue;
          memset(resp, -1, sizeof(resp));
          memset(dk, false, sizeof(dk));
          if (checkmask == mask) continue;
          resp[xini][yini] = 0;
          queue<pair<int, int> > cola;
          cola.push(make_pair(xini, yini));
          while (!cola.empty()) {
            int nx = cola.front().first;
            int ny = cola.front().second;
            cola.pop();
            if (dk[nx][ny]) continue;
            dk[nx][ny] = true;
            if (resp[nx][ny] > len) break;
            for (int i = 0; i < (int)(4); i++) {
              int mmx = nx + mx[i];
              int mmy = ny + my[i];
              if (!(mmx >= 0 && mmx < n && mmy >= 0 && mmy < m)) continue;
              int value = mapa[mmx][mmy] - 'a';
              if (!(mask & (1 << value)) && mapa[mmx][mmy] != 'T' &&
                  mapa[mmx][mmy] != 'S')
                continue;
              if (resp[mmx][mmy] == -1) {
                resp[mmx][mmy] = resp[nx][ny] + 1;
                cola.push(make_pair(mmx, mmy));
                path[mmx][mmy] = make_pair(nx, ny);
              } else if (resp[mmx][mmy] == resp[nx][ny] + 1) {
                int cur1x, cur1y, cur2x, cur2y;
                cur1x = path[mmx][mmy].first;
                cur1y = path[mmx][mmy].second;
                cur2x = nx;
                cur2y = ny;
                while (mapa[cur1x][cur1y] == mapa[cur2x][cur2y]) {
                  int tmp = path[cur1x][cur1y].first;
                  cur1y = path[cur1x][cur1y].second;
                  cur1x = tmp;
                  tmp = path[cur2x][cur2y].first;
                  cur2y = path[cur2x][cur2y].second;
                  cur2x = tmp;
                  if ((cur1x == cur2x && cur1y == cur2y)) break;
                }
                if (mapa[cur1x][cur1y] >= mapa[cur2x][cur2y]) {
                  path[mmx][mmy] = make_pair(nx, ny);
                }
              }
            }
          }
          if (resp[xfin][yfin] != -1) {
            string aux = recover(xfin, yfin);
            if (resp[xfin][yfin] < len) {
              result = aux;
              len = resp[xfin][yfin];
            } else if (resp[xfin][yfin] == len) {
              if (result == ">" || result > aux) result = aux;
            }
          }
          checkmask = mask;
        }
      }
    }
  }
  if (result == ">") return "-1";
  return result;
}
int main() {
  scanf("%d%d%d", &n, &m, &kk);
  for (int i = 0; i < (int)(n); i++) {
    scanf("%s", mapa[i]);
    for (int j = 0; j < (int)(m); j++) {
      if (mapa[i][j] == 'T') {
        xini = i;
        yini = j;
      } else if (mapa[i][j] == 'S') {
        xfin = i;
        yfin = j;
      }
    }
  }
  cout << bfs() << endl;
  return 0;
}