У вас есть таблица c
N строками и
M столбцами. В каждой ячейке таблицы записана одна строчная буква английского алфавита. Рассмотрим все возможные пути от левого верхнего угла до правого нижнего угла, если вам разрешено идти только вправо и вниз. Конкатенация букв в порядке обхода составляют строку. Скажем, что эта строка - значение пути. Теперь рассмотрим все такие пути и отсортируем их значения в алфавитном порядке. Ваша задача найти значение
K-го пути в этом отсортированном листе.
Входные данные
В первой строке задается два целых числа
N - количество рядов и
M - количество столбцов заданной таблицы (1 <=
N,
M <= 30). Каждая из следующих
N строк содержит ровно
M строчных букв английского алфавита. Последняя строка входного файла содержит целое число
K (1 <=
K <= 10
18). Гарантируется, что для
K ответ всегда существует.
Выходные данные
Выведите ответ на задачу
Пояснения к примеру
abcdgk, abcdgk, abcdjk, abfdgk, abfdjk, abfijk, aefdgk, aefdjk, aefijk, aehijk
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 4
abcd
efdg
hijk
4 |
abfdgk |