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 MAXN = 54;
const int MAXD = 5000;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {-1, 0, 1, 0};
static int d0;
bool valid[256];
int r, c;
char buf[MAXN][MAXN];
int d[MAXN][MAXN], p[MAXN][MAXN];
string gao(int sx, int sy) {
  queue<pair<int, int> > q;
  vector<vector<pair<int, int> > > v;
  static int x, y, xx, yy, z;
  d[sx][sy] = d0;
  q.push(make_pair(sx, sy));
  while (!q.empty()) {
    x = q.front().first;
    y = q.front().second;
    z = d[x][y] + 1;
    v.resize(z - d0 + 1);
    v[z - d0].push_back(make_pair(x, y));
    q.pop();
    if (buf[x][y] == 'S') {
      break;
    }
    for (int i = 0; i < 4; ++i) {
      xx = x + dx[i];
      yy = y + dy[i];
      if (valid[(int)buf[xx][yy]] && d[xx][yy] > z) {
        d[xx][yy] = z;
        q.push(make_pair(xx, yy));
      }
    }
  }
  if (buf[x][y] != 'S') {
    return "~";
  } else {
    for (int i = 0; i < (int)v.size(); ++i) {
      vector<pair<pair<char, int>, pair<int, int> > > w;
      for (int j = 0; j < (int)v[i].size(); ++j) {
        x = v[i][j].first;
        y = v[i][j].second;
        w.push_back(make_pair(make_pair(buf[x][y], MAXD), make_pair(x, y)));
        for (int k = 0; k < 4; ++k) {
          xx = x + dx[k];
          yy = y + dy[k];
          if (d[xx][yy] == d[x][y] - 1) {
            w.back().first.second = min(w.back().first.second, p[xx][yy]);
          }
        }
      }
      sort(w.begin(), w.end());
      for (int j = 0; j < (int)w.size(); ++j) {
        p[w[j].second.first][w[j].second.second] = j;
      }
    }
    string ret;
    while (true) {
      sx = -1;
      sy = -1;
      for (int i = 0; i < 4; ++i) {
        xx = x + dx[i];
        yy = y + dy[i];
        if (d[xx][yy] == d[x][y] - 1 && (sx == -1 || p[xx][yy] < p[sx][sy])) {
          sx = xx;
          sy = yy;
        }
      }
      if (buf[sx][sy] == 'T') {
        break;
      } else {
        ret += buf[sx][sy];
      }
      x = sx;
      y = sy;
    }
    return ret;
  }
}
int main() {
  int n, sx = -1, sy = -1, tx = -1, ty = -1;
  bool select[MAXN];
  string ans, tmp;
  scanf("%d%d%d", &r, &c, &n);
  memset(buf, '~', sizeof(buf));
  for (int i = 1; i <= r; ++i) {
    scanf("%s", buf[i] + 1);
    for (int j = 1; j <= c; ++j) {
      if (buf[i][j] == 'S') {
        sx = i;
        sy = j;
      } else if (buf[i][j] == 'T') {
        tx = i;
        ty = j;
      }
    }
    buf[i][c + 1] = '~';
  }
  fill(select, select + 26, false);
  fill(select, select + n, true);
  sort(select, select + 26);
  valid['S'] = valid['T'] = true;
  ans = "~";
  d0 = 0;
  do {
    d0 -= MAXD;
    for (int i = 0; i < 26; ++i) {
      valid['a' + i] = select[i];
    }
    tmp = gao(tx, ty);
    if (tmp != "~" && (ans == "~" || tmp.length() < ans.length() ||
                       (tmp.length() == ans.length() && tmp < ans))) {
      ans = tmp;
    }
  } while (next_permutation(select, select + 26));
  if (ans == "~") {
    puts("-1");
  } else {
    puts(ans.c_str());
  }
  return 0;
}