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;
vector<vector<set<int> > > setgrid;
vector<string> grid;
int k;
int ro[4] = {1, -1, 0, 0};
int co[4] = {0, 0, -1, 1};
struct s {
  s() : r(-1), c(-1), set(-1), path(""), let('A'), d(0) {}
  s(int nr, int nc, unsigned int nset, string npath, char nlet, int nd)
      : r(nr), c(nc), set(nset), path(npath), let(nlet), d(nd) {}
  int r, c, d;
  unsigned int set;
  string path;
  char let;
};
bool operator<(const s &lhs, const s &rhs) {
  if (lhs.d == rhs.d)
    if (lhs.path == rhs.path)
      return lhs.let >= rhs.let;
    else
      return lhs.path >= rhs.path;
  else
    return lhs.d >= rhs.d;
}
bool visited(int r, int c, unsigned int set) {
  unsigned int subset = set;
  do {
    subset = (subset - 1) & set;
    if (setgrid[r][c].find(subset) != setgrid[r][c].end()) {
      return true;
    }
  } while (subset != set);
  return false;
}
int main(void) {
  s qf;
  int rs, cs, nr, nc;
  unsigned int nset, one = 0x00000001;
  priority_queue
 q;
  vector
 pv, tv;
  cin >> rs >> cs >> k;
  grid.resize(rs);
  for (int i = 0; i < rs; i++) cin >> grid[i];
  setgrid.resize(rs);
  for (int i = 0; i < rs; i++) setgrid[i].resize(cs);
  int sr, sc;
  for (int i = 0; i < rs; i++)
    for (int j = 0; j < cs; j++)
      if (grid[i][j] == 'S') {
        sr = i;
        sc = j;
        break;
      }
  q.push(s(sr, sc, 0, "", 'a', 0));
  setgrid[sr][sc].insert(0);
  while (!q.empty()) {
    pv.clear();
    qf = q.top();
    for (int i = 0; i < 4; i++) {
      nr = qf.r + ro[i];
      nc = qf.c + co[i];
      if (nr < 0 || nr >= rs || nc < 0 || nc >= cs) continue;
      if (grid[nr][nc] == 'T') goto success;
      nset = qf.set | (one << int(grid[nr][nc] - 'a'));
      if ((__builtin_popcount(nset) > k) || visited(nr, nc, nset)) continue;
      pv.push_back(
          s(nr, nc, nset, qf.path + grid[nr][nc], grid[nr][nc], qf.d + 1));
      setgrid[nr][nc].insert(nset);
    }
    sort(pv.begin(), pv.end());
    for (int i = 0; i < pv.size(); i++) q.push(pv[i]);
    q.pop();
  }
  cout << -1 << '\n';
  return 0;
success:
  if (qf.path != "") cout << qf.path << '\n';
  return 0;
}