Задача B. Головоломная лотерея

Автор:A. Klenin   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:128 Мб
Выходной файл:output.txt  

Условие

Журнал кроссвордов опубликовал новую головоломку. Она представляет собой квадрат размером N × N, в каждую клетку которого вписана малая латинская буква. Последовательности букв, которые можно построить, начиная с некоторой клетки и перемещаясь на соседние по горизонтали и вертикали, назовём словами. При построении слова запрещено дважды посещать одну и ту же клетку.

Приз достанется читателю, первым нашедшему слово длиной L, которое можно построить наибольшим количеством способов. Среди слов с равным количеством способов следует выбрать первое в лексикографическом порядке.

Формат входного файла

Первая строка содержит числа N L, далее идут N строк по N символов в каждой.

Формат выходного файла

Файл должен содержать единственную строку из L символов — наиболее часто встречающееся слово.

Ограничения

1 ≤ N ≤ 35, 1 ≤ L ≤ 8, L ≤ N2

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 2
ba
ac
ab
2
5 3
adfaf
cadda
bbeae
edecb
fdecc
ada

0.107s 0.015s 13