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:
//package round72;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class C3 {
	Scanner in;
	PrintWriter out;
//	String INPUT = "5 3 2\r\n" +
//	"Sba\r\n" +
//	"ccc\r\n" +
//	"aac\r\n" +
//	"ccc\r\n" +
//	"abT";
//	String INPUT = "3 4 1\r\n" +
//			"Sxyy\r\n" +
//			"yxxx\r\n" +
//			"yyyT";
//	String INPUT = "1 3 3\r\n" +
//			"TyS";
//	String INPUT = "1 4 1\r\n" +
//	"SxyT";
	String INPUT = "";
	
	int sr, sc, gr, gc;
	char[][] map;
	
	void solve()
	{
		n = ni();
		m = ni();
		k = ni();
		map = new char[n][m];
		sr = 0; sc = 0; gr = 0; gc = 0;
		for(int i = 0;i < n;i++){
			map[i] = in.next().toCharArray();
			for(int j = 0;j < m;j++){
				if(map[i][j] == 'S'){
					sr = i;
					sc = j;
				}
				if(map[i][j] == 'T'){
					gr = i;
					gc = j;
				}
			}
		}
		
		StringBuilder sb = new StringBuilder("~");
		for(int i = 0;i < 14;i++)sb.append(sb);
		opt = sb.toString();
		int o = opt.length();
		path = new String[n*m];
		d = new int[n*m];
		poss = new boolean[n*m];
		if(k == 4){
			for(int a = 0;a < 26;a++){
				for(int b = a+1;b < 26;b++){
					for(int c = b+1;c < 26;c++){
						for(int d = c+1;d < 26;d++){
							int code = 1<<a|1<<b|1<<c|1<<d;
							simulate(code);
						}
					}
				}
			}
		}else if(k == 3){
			for(int a = 0;a < 26;a++){
				for(int b = a+1;b < 26;b++){
					for(int c = b+1;c < 26;c++){
						simulate(1<<a|1<<b|1<<c);
					}
				}
			}
		}else if(k == 2){
			for(int a = 0;a < 26;a++){
				for(int b = a+1;b < 26;b++){
					simulate(1<<a|1<<b);
				}
			}
		}else{
			for(int a = 0;a < 26;a++){
				simulate(1<<a);
			}
		}
		
		if(opt.length() == o) {
			out.println(-1);
		}else {
			out.println(opt);
		}
	}
	
	int[] d;
	String[] path;
	boolean[] poss;
	String opt;
	Q q = new Q(10000);
	
	public void simulate(int ok)
	{
		q.clear();
		q.add(sr*m+sc);
		Arrays.fill(d, INF);
		d[sr*m+sc] = 0;
		while(!q.isEmpty()){
			int cur = q.poll();
			int r = cur / m;
			int c = cur % m;
			for(int i = 0;i < 4;i++){
				int nr = r + dr[i];
				int nc = c + dc[i];
				if(nr >= 0 && nr < n && nc >= 0 && nc < m &&
					(map[nr][nc] == 'T' || ok<<31-(map[nr][nc]-'a')<0) && d[nr*m+nc] > d[cur] + 1) {
					d[nr*m+nc] = d[cur] + 1;
					q.add(nr*m+nc);
				}
			}
		}
		if(d[gr*m+gc] <= opt.length() + 1) {
			Arrays.fill(poss, false);
			Arrays.fill(path, null);
			q.add(sr*m+sc);
			poss[sr*m+sc] = true;
			path[sr*m+sc] = "";
			while(q.size() > 0) {
				int cur = q.poll();
				int r = cur / m;
				int c = cur % m;
				String candi = null;
				for(int i = 0;i < 4;i++){
					int nr = r + dr[i];
					int nc = c + dc[i];
					if(nr >= 0 && nr < n && nc >= 0 && nc < m) {
						if(d[nr*m+nc] == d[cur] - 1) {
							if(candi == null || path[nr*m+nc].compareTo(candi) < 0) {
								candi = path[nr*m+nc];
							}
						}else if(d[nr*m+nc] == d[cur] + 1 && !poss[nr*m+nc]) {
							poss[nr*m+nc] = true;
							q.add(nr*m+nc);
						}
					}
				}
				if(candi != null) {
					if(map[r][c] == 'T') {
						if(candi.length() < opt.length() || candi.length() == opt.length() && candi.compareTo(opt) < 0){
							opt = candi;
						}
						break;
					}else {
						path[cur] = candi + map[r][c];
					}
				}
			}
		}
	}
	
	int INF = 99999999;
	
	int[] dr = {1,0,-1,0};
	int[] dc = {0,1,0,-1};
	int m, n, k;
	
	void run() throws Exception
	{
//		int n = 50;
//		StringBuilder sb = new StringBuilder(n + " " + n + " 4 ");
//		Random r = new Random();
//		for(int i = 0;i < n;i++){
//			for(int j = 0;j < n;j++) {
//				if(i == 0 && j == 0) {
//					sb.append('S');
//				}else if(i == n - 1 && j == n - 1) {
//					sb.append('T');
//				}else {
//					sb.append((char)(r.nextInt(1)+'a'));
//				}
//			}
//			sb.append(" ");
//		}
//		INPUT = sb.toString();
//
//		long s = System.currentTimeMillis();
		in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT);
		out = new PrintWriter(System.out);

		solve();
		out.flush();
//		long g = System.currentTimeMillis();
//		tr(g-s+"ms");
	}
	
	public static class Q {
		public int[] q;
		protected int pt, ph;
		public Q(int n){ q = new int[n]; pt = ph = 0; }
		public void add(int x){ q[ph++] = x; }
		public void clear(){ pt = ph = 0; }
		public int poll(){ return q[pt++]; }
		public int size(){ return ph-pt; }
		public boolean isEmpty(){ return ph==pt; }
	}
	
	public static void main(String[] args) throws Exception
	{
		new C3().run();
	}
	
	int ni() { return Integer.parseInt(in.next()); }
	double nd() { return Double.parseDouble(in.next()); }
	void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}