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: 2011-05-13
Last Updated: 2011-05-13

This code gets Accepted on CodeForces Practice.
*/

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

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

	public int oo = 987654321;	
	//Down, Up, Right, Left
	public int[] dx = { 1,-1, 0, 0};
	public int[] dy = { 0, 0, 1,-1};
		
    private class Pair
    {
        public final int x, y;
        public Pair(int xx, int yy) { x = xx; y = yy; }
        
        public boolean equals(Pair u)
        {
        	return x == u.x && y == u.y;
        }
    }	
	
	public int rn, cn, maxK;
	public char[][] A;
	
	//S: boolean indicating whether a character type can be used
    public boolean[] S;
    //can[i][j]: whether cell (i, j) can be used
    public boolean[][] can;
    //cost[i][j]: shortest path cost from source to cell (i, j)
    public int[][] cost;
	
    //all: array of the set of character types on the map.
    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 = ca2ba(CTS2ca(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); process(); }
		else
		{
			int Bound = all.length - maxK + i;
			while(x <= Bound)
			{
				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.equals(dst)) { break outter; }
				}
			}
		}

		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];
		
		Q.clear();
		mark[dst.x][dst.y] = true;
		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)
				{
					mark[pp.x][pp.y] = true;
					Q.offer(pp);
				}
			}
		}
		
		StringBuffer path = new StringBuffer("");		

		Q.clear(); Q.offer(sor);
		
		int C = cost[dst.x][dst.y];
		//C - 1 iterations
		for(int i = 1; i < C; ++i)
		{
			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 AlphaComparator());
			
			Pair p = list.get(0);
			char ch = A[p.x][p.y];
			
			path.append(ch);
			
			Q.clear();
			for(Pair t : list)
			{
				if(A[t.x][t.y] == ch) Q.offer(t);
				else { break; }
			}
		}//ends for(int i = 1; i < C; ++i)
		
		best = better(best, path.toString());
	}//end public void process()
	
	private class AlphaComparator implements Comparator<Pair>
	{
		public int compare(Pair a, Pair b)
		{
			return A[a.x][a.y] - A[b.x][b.y];
		}
	}
	
    public boolean valid(Pair p) { return 0 <= p.x && p.x < rn && 0 <= p.y && p.y < cn; }
		
	public void init(int[][] A, int 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;
		
		int c = A.compareTo(B);
		if(c < 0) return A;
		if(c > 0) return B;
		
		return A;
	}
		
	public boolean[] ca2ba(char[] v)
	{
		boolean[] r = new boolean[26];
		for(char c : v) r[c - '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 static void main(String[] args)
	{
		(new Track()).main();
	}
}