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 = 51;
const int go[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
char q[maxn];
int a[maxn][maxn];
int b[maxn][maxn];
int now[4];
int k;
int str[(int)1e6][4];
int number;
void genmasks(int iter) {
  if (iter == k) {
    for (int i = 0; i < k; i++) str[number][i] = now[i];
    number++;
    return;
  }
  int start = 0;
  if (iter) start = now[iter - 1] + 1;
  for (int i = start; i < 26; i++) {
    now[iter] = i;
    genmasks(iter + 1);
  }
}
char strnow[maxn * maxn + 1], strans[maxn * maxn + 1];
pair<int, int> st[maxn * maxn * 10];
pair<int, int> pr[maxn][maxn];
int cl[maxn][maxn];
int dist[maxn][maxn];
vector<int> cnt(4, 0);
vector<int> heads(4, 0);
int main() {
  int w, h;
  while (scanf("%d%d%d", &h, &w, &k) >= 2) {
    pair<int, int> start, finish;
    for (int i = 0; i < h; i++) {
      scanf("%s", q);
      for (int j = 0; j < w; j++) {
        a[i][j] = (q[j] - 'a');
        if (q[j] == 'S') {
          a[i][j] = -2;
          start = make_pair(i, j);
        }
        if (q[j] == 'T') {
          a[i][j] = -2;
          finish = make_pair(i, j);
        }
      }
    }
    number = 0;
    genmasks(0);
    int distans = ((int)1E9) - 2;
    for (int mask = 0; mask < number; mask++) {
      for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
          dist[i][j] = ((int)1E9);
          pr[i][j] = make_pair(-1, -1);
          cl[i][j] = 0;
          b[i][j] = -1;
          for (int y = 0; y < k; y++)
            if (str[mask][y] == a[i][j]) {
              b[i][j] = y;
              break;
            }
          if (a[i][j] == -2) b[i][j] = k;
        }
      }
      int cool = 0;
      st[0] = start;
      dist[start.first][start.second] = 0;
      for (int l = 0, r = 1; l < r;) {
        int l0 = l, r0 = r;
        int cool0 = cl[st[l].first][st[l].second],
            dist0 = dist[st[l0].first][st[l0].second];
        while (l < r) {
          int y = st[l].first, x = st[l].second;
          if (dist[y][x] > dist0) {
            cool = 0;
            break;
          }
          if (cl[y][x] != cool0) {
            cool += 4;
            break;
          }
          for (int g = 0; g < 4; g++) {
            int yn = y + go[g][0], xn = x + go[g][1];
            if (yn < 0 || xn < 0 || yn >= h || xn >= w) continue;
            if (b[yn][xn] == -1) continue;
            if (dist[yn][xn] <= dist[y][x]) continue;
            if ((dist[yn][xn] == dist[y][x] + 1) &&
                (cl[yn][xn] <= cool + b[yn][xn]))
              continue;
            dist[yn][xn] = dist[y][x] + 1;
            cl[yn][xn] = cool + b[yn][xn];
            pr[yn][xn] = make_pair(y, x);
            if (b[yn][xn] != k) st[r++] = make_pair(yn, xn);
          }
          l++;
        }
        for (int i = 0; i < k; i++) cnt[i] = 0, heads[i] = 0;
        for (int i = r0; i < r; i++) {
          cnt[cl[st[i].first][st[i].second] & 3]++;
        }
        heads[0] = r0;
        for (int i = 1; i < k; i++) heads[i] = heads[i - 1] + cnt[i - 1];
        for (int iter = 0; iter < k; iter++) {
          for (int i = heads[iter]; i < r; i++) {
            int m = cl[st[i].first][st[i].second] & 3;
            if (m == iter) {
              swap(st[heads[iter]], st[i]);
              heads[iter]++;
            }
          }
        }
      }
      if (dist[finish.first][finish.second] - 1 > distans) continue;
      int lenn = 0;
      int distn = dist[finish.first][finish.second];
      for (pair<int, int> now = pr[finish.first][finish.second]; now != start;
           now = pr[now.first][now.second]) {
        assert(distn - 1 == dist[now.first][now.second]);
        distn--;
        strnow[lenn++] = a[now.first][now.second] + 'a';
      }
      assert(lenn == dist[finish.first][finish.second] - 1);
      reverse(strnow, strnow + lenn);
      strnow[lenn] = 0;
      if ((lenn < distans) || (strcmp(strnow, strans) < 0)) {
        distans = lenn;
        for (int i = 0; i <= lenn; i++) strans[i] = strnow[i];
      }
    }
    if (distans == ((int)1E9) - 2)
      printf("-1\n");
    else
      printf("%s\n", strans);
  }
  return 0;
}