Вам дана матрица размера \(n \times n\), заполненная строчными латинскими буквами. Вы можете изменить не более \(k\) букв в этой матрице.
Рассмотрим все пути из верхней левой клетки в правую нижнюю, в которых каждая следующая клетка является соседней справа или снизу с предыдущей. Каждому пути соответствует строка, которая получается выписыванием подряд букв во всех клетках, через которые проходит этот путь. Таким образом длина каждого пути равна \(2n - 1\).
Найдите лексикографически минимальную строку, которая может соответствовать какому-то пути после того, как вы измените буквы в не более чем \(k\) клетках матрицы.
Строка \(a\) лексикографически меньше строки \(b\), если первая различная в \(a\) и \(b\) буква меньше в строке \(a\).
Выходные данные
Выведите лексикографически минимальную строку, которая может соответствовать какому-то пути после того, как вы измените не более чем \(k\) букв в матрице.
Примечание
В первом примере можно изменить буквы «b» в клетках \((2, 1)\) и \((3, 1)\) на «a», тогда лексикографически минимальный путь проходит через клетки \((1, 1), (2, 1), (3, 1), (4, 1), (4, 2), (4, 3), (4, 4)\). Первая координата описывает номер строки, вторая — номер столбца.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
abcd
bcde
bcad
bcde
|
aaabcde
|
|
2
|
5 3
bwwwz
hrhdh
sepsp
sqfaf
ajbvw
|
aaaepfafw
|
|
3
|
7 6
ypnxnnp
pnxonpm
nxanpou
xnnpmud
nhtdudu
npmuduh
pmutsnz
|
aaaaaaadudsnz
|