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:

/*

Author: Yiu Yu Ho
Creation: <Creation Date>
Last Updated: <Last Updated Date>
*/

import java.io.*;
import java.util.*;

public class Track
{
    public Scanner in = new Scanner(System.in);
    public PrintStream out = System.out;

    //int pair
    private class Pair implements Comparable<Pair>
    {
        public final int x, y;
        public Pair(int xx, int yy) { x = xx; y = yy; }

        public int compareTo(Pair u)
        {
            if(x!=u.x) return x-u.x;
            return y-u.y;
        }

        public String toString() { return "(" + x + "," + y + ")"; }
    }   
    
    public int rn, cn, maxK;
    public char[][] A; 
    public boolean[][] can;
    public int[][] cost;
    public boolean[] S;
    
    public char[] all;
    public Pair sor, dst;
    
    public String best = null;
    
    public void main()
    {
        rn = in.nextInt();
        cn = in.nextInt();
        maxK = in.nextInt();
        
        A = new char[rn][];
        for(int i = 0; i < rn; ++i) A[i] = in.next().toCharArray();
        
        TreeSet<Character> allSet = new TreeSet<Character>();
        
        for(int i = 0; i < rn; ++i)
        for(int j = 0; j < cn; ++j)
        {
            if(A[i][j] == 'S')
            {
                sor = new Pair(i, j);
            }
            else if(A[i][j] == 'T')
            {
                dst = new Pair(i, j);
            }
            else
            {
                allSet.add(A[i][j]);
            }
        }
        
        if(allSet.size() <= maxK)
        {
            S = CTS2ba(allSet);
            process();
        }
        else
        {
            all = CTS2ca(allSet);
            combination(new char[maxK], 0, 0);
        }
        
        if(best == null)
        {
            out.println(-1);
        }
        else
        {
            out.println(best);
        }
    }//end public void main()

    public void combination(char[] v, int i, int x)
    {
        if(i >= v.length)
        {
            S = ca2ba(v);
            //System.err.println("v = " + Arrays.toString(v));
            process();
        }
        else
        {
            while(x <= all.length - maxK + i)
            {
                v[i] = all[x];
                combination(v, i+1, x+1);
                ++x;
            }
        }
    }
    
    public void process()
    {
        can = new boolean[rn][cn];
        
        for(int i = 0; i < rn; ++i)
        for(int j = 0; j < cn; ++j)
        {
            if(A[i][j] == 'S' || A[i][j] == 'T' || S[A[i][j] - 'a'])
            {
                can[i][j] = true;
            }
        }
        
        cost = new int[rn][cn];
        init(cost, oo);
        
        Queue<Pair> Q = new LinkedList<Pair>();
        cost[sor.x][sor.y] = 0;
        Q.offer(sor);
        
outter:     
        while(!Q.isEmpty())
        {
            Pair p = Q.poll();
            int c = cost[p.x][p.y];
            
            for(int dir = 0; dir < dx.length; ++dir)
            {
                Pair pp = new Pair(p.x + dx[dir], p.y + dy[dir]);
                if(!valid(pp)) continue;                
                if(!can[pp.x][pp.y]) continue;
                
                if(c + 1 < cost[pp.x][pp.y])
                {
                    cost[pp.x][pp.y] = c + 1;
                    Q.offer(pp);
                    
                    if(pp.compareTo(dst) == 0) break outter;
                }
            }
        }
        
        //System.err.println("cost = " + cost[dst.x][dst.y]);
        
        if(cost[dst.x][dst.y] >= oo) return;
        if(best != null && cost[dst.x][dst.y] > best.length() + 1) return;
        
        boolean[][] mark = new boolean[rn][cn];
        
        mark[dst.x][dst.y] = true;
        Q.clear();
        Q.offer(dst);
        while(!Q.isEmpty())
        {
            Pair p = Q.poll();
            int c = cost[p.x][p.y];
            
            for(int dir = 0; dir < dx.length; ++dir)
            {
                Pair pp = new Pair(p.x + dx[dir], p.y + dy[dir]);
                if(!valid(pp)) continue;
                if(!can[pp.x][pp.y]) continue;
                if(mark[pp.x][pp.y]) continue;
                
                if(cost[pp.x][pp.y] + 1 == c)
                {
                    Q.offer(pp);
                    mark[pp.x][pp.y] = true;
                }
            }
        }
        
        //print(mark);
        
        StringBuffer path = new StringBuffer("");       

        Q.clear();
        Q.offer(sor);
        
        while(true)
        {
            ArrayList<Pair> list = new ArrayList<Pair>();
            
            while(!Q.isEmpty())
            {
                Pair p = Q.poll();
                int c = cost[p.x][p.y];
                
                for(int dir = 0; dir < dx.length; ++dir)
                {
                    Pair pp = new Pair(p.x + dx[dir], p.y + dy[dir]);
                    
                    if(!valid(pp)) continue;
                    if(!mark[pp.x][pp.y]) continue;
                    
                    if(cost[pp.x][pp.y] == c + 1)
                    {
                        mark[pp.x][pp.y] = false;
                        list.add(pp);
                    }
                }
            }
            
            Collections.sort(list, new PairComparator());
            
            Pair p = list.get(0);
            char ch = A[p.x][p.y];
            
            if(ch == 'T') break;        
            path.append(ch);
            
            Q.clear();
            for(int i = 0; i < list.size(); ++i)
            {
                p = list.get(i);
                if(A[p.x][p.y] == ch)
                {
                    Q.offer(p);
                }
                else
                {
                    break;
                }
            }
        }//ends while(true)
        
        best = better(best, path.toString());
    }//end public void process()
    
    private class PairComparator implements Comparator<Pair>
    {
        public int compare(Pair a, Pair b)
        {
            return A[a.x][a.y] - A[b.x][b.y];
        }
    }
    
    public boolean valid(int x,int y) { return 0 <= x && x < rn && 0 <= y && y < cn; }  
    public boolean valid(Pair p) { return valid(p.x, p.y); }
    
    public int oo = 987654321;  
    //Down, Up, Right, Left
    public int[] dx = { 1,-1, 0, 0};
    public int[] dy = { 0, 0, 1,-1};
    
    public void init(int[][] A, int val) 
    { 
        for(int i=0;i<A.length;++i) Arrays.fill(A[i], val); 
    }   
    
    public void init(boolean[][] A, boolean val)
    { 
        for(int i=0;i<A.length;++i) Arrays.fill(A[i], val); 
    }   
    
    public String better(String A, String B)
    {
        if(A == null) return B;
        if(B == null) return A;
        
        if(A.length() < B.length()) return A;
        if(B.length() < A.length()) return B;
        
        if(A.compareTo(B) < 0) return A;
        if(B.compareTo(A) < 0) return B;
        
        return A;
    }
    
    public boolean[] CTS2ba(TreeSet<Character> set)
    {
        boolean[] r = new boolean[26];
        for(Character c : set) r[c - 'a'] = true;
        return r;
    }   
    
    public boolean[] ca2ba(char[] v)
    {
        boolean[] r = new boolean[26];
        for(int i = 0; i < v.length; ++i) r[v[i] - 'a'] = true;
        return r;
    }
    
    public static char[] CTS2ca(TreeSet<Character> S)
    {
        char[] r = new char[S.size()];
        int i = 0;
        for(Character c : S)
        {
            r[i] = c;
            ++i;
        }
        return r;
    }   
    
    public void print(boolean[][] B)
    {
        for(int i = 0; i < B.length; ++i)
        {
            for(int j = 0; j < B[i].length; ++j) out.print(B[i][j] ? '1' : '0');
            out.println();
        }
    }
    
    public static void main(String[] args)
    {
        (new Track()).main();
    }
}