题目描述

给定一个 $n$ × $m$ 的正方形网格。除起始方块（用 S 标记）和终止方块（用 T 标记）外，每个方块都用小写字母标记。

从一个正方形移动到另一个正方形的时间等于 $1$ 分钟。你只能从一个正方形移动到相邻正方形，但不能超出矩阵图边缘。此外，不允许访问超过 $k$ 种不同类型的方格。标有 S 和 T 的正方形没有类型，不用计算。

你需要输出从方块 S 块 T 间最短的路径所经过的所有方块（不包含 S 和 T）。如有多条最短路径，输出字典序最小的一条。

输入格式

第一行三个整数 $n,m,k$，$1\le n,m\le 50,n·m\ge 2,1\le k\le 4$。

接下来 $n$ 行描述网格，保证起点和终点唯一。

输出格式

如果存在最短路径，在一行中输出最短路径。若不存在，输出 $-1$。

最短路径可能为空，则什么都不输出。

5 3 2
Sba
ccc
aac
ccc
abT

bcccc

3 4 1
Sxyy
yxxx
yyyT

xxxx

1 3 3
TyS

y

1 4 1
SxyT

-1