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 int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 53;
const int BASE = 26;
const int MOVE[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
struct cT {
  cT() : x(0), y(0) {}
  cT(int _x, int _y) : x(_x), y(_y) {}
  int x, y;
};
int n, m, k;
char sg[MAXN][MAXN];
int a[MAXN][MAXN];
cT S, T;
bool cho[MAXN];
int nans, ans[MAXN * MAXN], cur[MAXN * MAXN];
int lev[MAXN][MAXN];
cT q[MAXN * MAXN];
int tc[2];
cT nq[2][MAXN * MAXN];
void init();
void input();
void work();
void dfs(int now, int nk);
void check();
inline bool ok(int x, int y) {
  return (x > 0 && x <= n && y > 0 && y <= m &&
          (sg[x][y] == 'S' || sg[x][y] == 'T' || cho[a[x][y]]));
}
int main() {
  init();
  input();
  work();
}
void init() { ios::sync_with_stdio(false); }
void input() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 1; i <= n; ++i) scanf("%s", sg[i] + 1);
}
void work() {
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      a[i][j] = sg[i][j] - 'a';
      if (sg[i][j] == 'S')
        S = cT(i, j);
      else if (sg[i][j] == 'T')
        T = cT(i, j);
    }
  nans = INF;
  dfs(0, 0);
  if (nans == INF)
    printf("-1\n");
  else {
    for (int i = 1; i < nans; ++i) putchar(ans[i] + 'a');
    putchar('\n');
  }
}
void dfs(int now, int nk) {
  if (nk > k) return;
  if (now >= BASE) {
    check();
  } else {
    cho[now] = false;
    dfs(now + 1, nk);
    cho[now] = true;
    dfs(now + 1, nk + 1);
  }
}
void check() {
  int l = 0, r = 0;
  cT now, v;
  q[r++] = T;
  memset(lev, -1, sizeof(lev));
  lev[T.x][T.y] = 0;
  while (l < r) {
    now = q[l++];
    for (int d = 0; d < 4; ++d) {
      v = cT(now.x + MOVE[d][0], now.y + MOVE[d][1]);
      if (ok(v.x, v.y) && (lev[v.x][v.y] == -1)) {
        lev[v.x][v.y] = lev[now.x][now.y] + 1;
        q[r++] = v;
      }
    }
  }
  if (lev[S.x][S.y] == -1 || lev[S.x][S.y] > nans) return;
  int nc = 0, nmin, lmin;
  now = S;
  cT mv;
  int t = 0;
  nq[t][tc[t]++] = S;
  lmin = a[S.x][S.y];
  for (int i = 1; i < lev[S.x][S.y]; ++i) {
    nmin = INF;
    tc[t ^ 1] = 0;
    for (int j = 0; j < tc[t]; ++j) {
      now = nq[t][j];
      if (a[now.x][now.y] == lmin) {
        for (int d = 0; d < 4; ++d) {
          v = cT(now.x + MOVE[d][0], now.y + MOVE[d][1]);
          if (ok(v.x, v.y) && (lev[v.x][v.y] == lev[now.x][now.y] - 1) &&
              (a[v.x][v.y] <= nmin)) {
            nmin = a[v.x][v.y];
            nq[t ^ 1][tc[t ^ 1]++] = v;
          }
        }
      }
    }
    cur[i] = nmin;
    lmin = nmin;
    t ^= 1;
  }
  if (lev[S.x][S.y] < nans) {
    nans = lev[S.x][S.y];
    for (int i = 1; i < nans; ++i) ans[i] = cur[i];
  } else {
    for (int i = 1; i < nans; ++i) {
      if (cur[i] < ans[i]) {
        for (int j = 1; j < nans; ++j) ans[j] = cur[j];
        return;
      } else if (cur[i] > ans[i])
        return;
    }
  }
}