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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;

public class C83 {

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        String[] T = in.readLine().split(" ");
        int n = Integer.valueOf(T[0]);
        int m = Integer.valueOf(T[1]);
        int k = Integer.valueOf(T[2]);
        int sx = -1, sy = -1;
        int fx = -1, fy = -1;
        char[][] map = new char[n][];
        for (int i = 0; i < n; i++) {
            map[i] = in.readLine().toCharArray();
            for (int j = 0; j < m; j++)
                if (map[i][j] == 'S') {
                    sx = i;
                    sy = j;
                }
                else if (map[i][j] == 'T') {
                    fx = i;
                    fy = j;
                }
        }       
        
        int[] p = new int[k];
        for (int i = 0; i < k; i++)
            p[i] = i;
        
        boolean[] b = new boolean[26];
        String ans = null;
        int best = Integer.MAX_VALUE;
        d = new int[n][m];
        x = new int[n*m];
        y = new int[n*m];
        char[] str = new char[n*m];
        
        boolean[][] g = new boolean[n][m];
        
        do {
            Arrays.fill(b, false);
            for (int i = 0; i < k; i++)
                b[p[i]] = true;
            for (int[] dd : d)
                Arrays.fill(dd, Integer.MAX_VALUE);
            start = 0;
            finish = 0;
            offer(fx, fy, 0);
            
            S : while (start > finish) {
                int curX = x[finish], curY = y[finish];
                finish++;
                for (int i = 0; i < dx.length; i++) {
                    int tox = curX + dx[i], toy = curY + dy[i];
                    if (tox < 0 || tox >= n || toy < 0 || toy >= m) continue;
                    if (d[tox][toy] != Integer.MAX_VALUE) continue;
                    if (map[tox][toy] == 'S') {
                        d[tox][toy] = d[curX][curY] + 1;
                        break S;
                    }
                    if (!b[map[tox][toy]-'a']) continue;
                    offer(tox, toy, d[curX][curY] + 1);
                }
            }
            
            if (d[sx][sy] != Integer.MAX_VALUE && d[sx][sy] <= best) {
                best = d[sx][sy];
            
                for (boolean[] gg : g)
                    Arrays.fill(gg, false);
                start = 0;
                finish = 0;
                x[start] = sx;
                y[start] = sy;
                g[sx][sy] = true;
                start++;
                Arrays.fill(str, 'z');
                str[0] = 'S';
                while (start > finish) {
                    int curX = x[finish], curY = y[finish];
                    finish++;
                    int dist = d[curX][curY];
                    if (str[best - dist] != map[curX][curY]) continue;
                    for (int i = 0; i < dx.length; i++) {
                        int tox = curX + dx[i], toy = curY + dy[i];
                        if (tox < 0 || tox >= n || toy < 0 || toy >= m) continue;
                        if (d[tox][toy] != dist - 1) continue;
                        if (map[tox][toy] < str[best - d[tox][toy]]) 
                            str[best - d[tox][toy]] = map[tox][toy];
                        if (g[tox][toy]) continue;
                        x[start] = tox;
                        y[start] = toy;
                        g[tox][toy] = true;
                        start++;
                    }
                }
                
                String cur = String.valueOf(str, 1, best-1);
                if (ans == null || cur.length() < ans.length() || cur.compareTo(ans) < 0) {
                    ans = cur;
                }
            }
            
        } while (next(p, k-1, 26));
        
        out.println(ans == null ? -1 : ans);

        out.flush();
    }
    
    static int[] dx = new int[]{1, -1, 0, 0};
    static int[] dy = new int[]{0, 0, 1, -1};
    
    static int[][] d;
    static int[] x;
    static int[] y;
    static int start = 0, finish = 0;
    
    static void offer(int tox, int toy, int dist) {
        x[start] = tox;
        y[start] = toy;
        d[tox][toy] = dist;
        start++;
    }
    
    static boolean next(int[] p, int k, int n) {
        p[k]++;
        if (p[k] >= n) {
            if (k == 0) return false;
            boolean res = next(p, k-1, n-1);
            p[k] = p[k-1]+1;
            return res;
        }
        else {
            return true;
        }
    }
}