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(1010101010);
const int dy[4] = {0, -1, 0, 1};
const int dx[4] = {1, 0, -1, 0};
string bin(int x, int le) {
  string ret;
  for (int i(0); i < (le); i++) ret += '0' + (x % 2), x /= 2;
  reverse((ret).begin(), (ret).end());
  return ret;
}
int h, w;
vector<string> veld(50);
typedef int Mat[50][50];
Mat ds, dt;
inline bool outofbounds(int y, int x) {
  return y >= h || y < 0 || x >= w || x < 0;
}
inline bool ok(char ch, int bm) {
  return ch == 'S' || ch == 'T' || bm & (1 << (ch - 'a'));
}
void bfs(int bm, pair<int, int> src, Mat& d) {
  for (int i(0); i < (h); i++)
    for (int j(0); j < (w); j++) d[i][j] = inf;
  d[src.first][src.second] = 0;
  deque<pair<int, int> > q;
  for (int i(0); i < (h); i++)
    for (int j(0); j < (w); j++) q.push_back(src);
  while (((int)(q).size())) {
    int y1(q.front().first), x1(q.front().second);
    q.pop_front();
    for (int dir(0); dir < (4); dir++) {
      int y2(y1 + dy[dir]), x2(x1 + dx[dir]);
      if (!outofbounds(y2, x2) && (ok(veld[y2][x2], bm))) {
        int d2(d[y1][x1] + 1);
        if (d2 < d[y2][x2]) {
          d[y2][x2] = d2;
          q.push_back(make_pair(y2, x2));
        }
      }
    }
  }
}
bool seen[55][55];
string bfs(int bm) {
  pair<int, int> s, t;
  for (int i(0); i < (h); i++)
    for (int j(0); j < (w); j++) {
      if (veld[i][j] == 'S') s = make_pair(i, j);
      if (veld[i][j] == 'T') t = make_pair(i, j);
    }
  bfs(bm, s, ds), bfs(bm, t, dt);
  int the_d(ds[t.first][t.second]);
  if (the_d == inf) {
    string ret;
    ret += 'z' + 1;
    return ret;
  }
  string pad;
  vector<pair<int, int> > doetmee;
  doetmee.push_back(s);
  for (int i(0); i < (50); i++)
    for (int j(0); j < (50); j++) seen[i][j] = false;
  seen[s.first][s.second] = true;
  while (true) {
    vector<pair<int, int> > doetmee2;
    assert(!((int)(doetmee2).size()));
    char nxt_chr('z');
    for (__typeof((doetmee).end()) it((doetmee).begin()); it != (doetmee).end();
         ++it) {
      int y1((*it).first), x1((*it).second);
      for (int dir(0); dir < (4); dir++) {
        int y2(y1 + dy[dir]), x2(x1 + dx[dir]);
        if (outofbounds(y2, x2)) continue;
        if (ds[y1][x1] + 1 + dt[y2][x2] == the_d) {
          if (y2 == t.first && x2 == t.second) {
            return pad;
          }
          nxt_chr = min(nxt_chr, veld[y2][x2]);
          doetmee2.push_back(make_pair(y2, x2));
        }
      }
    }
    pad += nxt_chr;
    doetmee.clear();
    for (__typeof((doetmee2).end()) it((doetmee2).begin());
         it != (doetmee2).end(); ++it) {
      int y((*it).first), x((*it).second);
      if (veld[y][x] == nxt_chr) {
        if (!seen[y][x]) {
          doetmee.push_back(*it);
          seen[y][x] = true;
        }
      }
    }
  }
}
string min1(string const& a, string const& b) {
  if (((int)(a).size()) < ((int)(b).size())) return a;
  if (((int)(a).size()) > ((int)(b).size())) return b;
  return min(a, b);
}
int main() {
  int k;
  cin >> h >> w >> k;
  for (int i(0); i < (h); i++) cin >> veld[i];
  string opt;
  for (int i(0); i < (1000); i++) opt += 'a';
  const int A(26);
  for (int bm(0); bm < (1 << (A));) {
    if (__builtin_popcount(bm) < k)
      bm++;
    else {
      string ans(bfs(bm));
      if (ans[0] != 'z' + 1) opt = min1(opt, ans);
      bm += bm & -bm;
    }
  }
  if (((int)(opt).size()) == 1000) {
    puts("-1");
  } else {
    cout << opt << endl;
  }
}