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;
struct timer {
  time_t start;
  timer() { start = clock(); }
  ~timer() {
    cerr << 1. * (clock() - start) / CLOCKS_PER_SEC << " secs" << endl;
  }
};
int n, m, K;
char c[55][55];
int sy, sx, ty, tx;
map<int, string> d[55][55];
int dy[] = {0, 1, 0, -1};
int dx[] = {1, 0, -1, 0};
string shortest[55][55];
int smask[55][55];
struct state {
  int y, x;
  string s;
  int mask;
  state(int y, int x, string s, int mask) : y(y), x(x), s(s), mask(mask) {}
};
const bool operator<(const state& a, const state& b) {
  return ((int)a.s.size()) > ((int)b.s.size()) ||
         ((int)a.s.size()) == ((int)b.s.size()) && a.s > b.s;
}
const bool better(string s, string t) {
  return ((int)s.size()) < ((int)t.size()) ||
         ((int)s.size()) == ((int)t.size()) && s < t;
}
int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cin >> n >> m >> K;
  for (int i = 1; i < (n + 1); i++)
    for (int j = 1; j < (m + 1); j++) {
      cin >> c[i][j];
      if (c[i][j] == 'S') sy = i, sx = j;
      if (c[i][j] == 'T') ty = i, tx = j;
    }
  for (int i = 1; i < (n + 1); i++)
    for (int j = 1; j < (m + 1); j++) {
      shortest[i][j] = string(n * m, '~');
    }
  d[sy][sx][0] = "";
  priority_queue<state> Q;
  Q.push(state(sy, sx, "", 0));
  while (((int)Q.size())) {
    state s = Q.top();
    Q.pop();
    if (s.y == ty && s.x == tx) {
      cout << s.s.substr(0, ((int)s.s.size()) - 1);
      return 0;
    }
    for (int i = 0; i < (4); i++) {
      int ny = s.y + dy[i], nx = s.x + dx[i];
      if (!c[ny][nx] || c[ny][nx] == 'S') continue;
      if (c[ny][nx] != 'T' && __builtin_popcount(s.mask) == K &&
          !(s.mask >> (c[ny][nx] - 'a') & 1))
        continue;
      string ndist = s.s + c[ny][nx];
      int nmask = s.mask | (c[ny][nx] == 'T' ? 0 : 1 << (c[ny][nx] - 'a'));
      if (!better(ndist, shortest[ny][nx]) &&
          (smask[ny][nx] & nmask) == smask[ny][nx])
        continue;
      if (shortest[ny][nx][0] == '~') {
        shortest[ny][nx] = ndist;
        smask[ny][nx] = nmask;
      }
      if (d[ny][nx].find(nmask) == d[ny][nx].end() ||
          better(ndist, d[ny][nx][nmask])) {
        d[ny][nx][nmask] = ndist;
        Q.push(state(ny, nx, ndist, nmask));
      }
    }
  }
  cout << -1;
}