Дано поле размера n × m, в каждой клетке которого записано по одной заглавной латинской букве. Вам необходимо найти такой маршрут длины k, что выписывая буквы из клеток на пути, полученная строка будет лексикографически минимальна. Из одной клетки можно пойти в другую, если у них есть общая сторона. Ходить за пределы поля и из клетку в саму себя не разрешается. Стартовать можно в любой клетке.
В первой строке даны три числа: n, m (1 ≤ n, m ≤ 100, n·m ≥ 2) – размеры поля и k (1 ≤ k ≤ 105) – длина строки. В следующих n строках записано ровно по m символов в каждой – описание поля. В таблице встречаются только латинские заглавные буквы.
Выведите лексикографически минимальную строку, которую можете получить, соблюдая описанные в условии ограничения.
1 4 1
BRZD
B
