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 JAVA):

Solution:
import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class C83 {
    
    static StringTokenizer st;
    static BufferedReader in;
    static int[]dx = {1, -1, 0, 0};
    static int[]dy = {0, 0, 1, -1};
    static int n,m;
    static int INF = (int) 1e9;
    static boolean[]possible;
    static int[][]a;
    static int[][]d;
    public static void main(String[] args) throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        n = nextInt();
        m = nextInt();
        int k = nextInt();
        int[]dx = {1, -1, 0, 0};
        int[]dy = {0, 0, 1, -1};
        a = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            String s = next();
            for (int j = 1; j <= m; j++) {
                a[i][j] = s.charAt(j-1)-96;
            }
        }
        int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a[i][j]+96=='S') {
                    y1 = i;
                    x1 = j;
                }
                if (a[i][j]+96=='T') {
                    y2 = i;
                    x2 = j;
                }
            }
        }
        int[]cols = new int[k+1];
        for (int i = 1; i <= k; i++) {
            cols[i] = i;
        }
        possible = new boolean[27];
        Queue<Point> q = new LinkedList<Point>(), possibles = new LinkedList<Point>();
        String ans = "";
        d = new int[n+1][m+1];
        boolean found = false;
        int[][]d1 = new int[n+1][m+1], d2 = new int[n+1][m+1];
        boolean[][]used = new boolean[n+1][m+1];
        while (true) {
            Arrays.fill(possible, false);
            for (int i = 1; i <= k; i++) {
                possible[cols[i]] = true;
            }
            bfs(x1, y1);
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    d1[i][j] = d[i][j];
                }
            }
            bfs(x2, y2);
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    d2[i][j] = d[i][j];
                }
            }
            d2 = d.clone();
            for (int i = 1; i <= n; i++) {
                Arrays.fill(used[i], false);
            }
            if (d1[y2][x2] != INF) {
                q.clear();
                q.add(new Point(x1, y1));
                used[y1][x1] = true;
                String res = "";
                for (int step = 1; step < d1[y2][x2]; step++) {
                    possibles.clear();
                    int min = 27;
                    for (Point p : q) {
                        int x = p.x, y = p.y;
                        for (int i = 0; i < 4; i++) {
                            int xx = x+dx[i], yy = y+dy[i];
                            if (xx >= 1 && xx <= m && yy >= 1 && yy <= n && !used[yy][xx] && d1[yy][xx]==step && d1[yy][xx]+d2[yy][xx]==d1[y2][x2]) {
                                possibles.add(new Point(xx, yy));
                                used[yy][xx] = true;
                                min = Math.min(min, a[yy][xx]);
                            }
                        }
                    }
                    q.clear();
                    for (Point p : possibles) {
                        if (a[p.y][p.x]==min) {
                            q.add(new Point(p.x, p.y));
                        }
                    }
                    res += (char)(min+96);
                }
                if (!found || res.length() < ans.length() || (res.length()==ans.length() && res.compareTo(ans) < 0))
                    ans = res;
                found = true;
            }
            int pos = k;
            while (pos > 0 && cols[pos]==26-(k-pos))
                pos--;
            if (pos==0)
                break;
            cols[pos]++;
            for (int i = pos+1; i <= k; i++) {
                cols[i] = cols[i-1]+1;
            }
        }
        if (!found)
            System.out.println(-1);
        else
            System.out.println(ans);
        pw.close();
    }
    private static void bfs(int x, int y) {
        for (int i = 1; i <= n; i++) {
            Arrays.fill(d[i], INF);
        }
        Queue<Point> q = new LinkedList<Point>();
        q.add(new Point(x, y));
        d[y][x] = 0;
        while (!q.isEmpty()) {
            x = q.peek().x;
            y = q.poll().y;
            for (int i = 0; i < 4; i++) {
                int xx = x+dx[i], yy = y+dy[i];
                if (xx >= 1 && xx <= m && yy >= 1 && yy <= n && d[yy][xx]==INF && (a[yy][xx] < 0 || possible[a[yy][xx]])) {
                    q.add(new Point(xx, yy));
                    d[yy][xx] = d[y][x]+1;
                }
            }
        }
    }
    private static int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    
    private static long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    
    private static double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    
    private static String next() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
}