5 Maratona NexTI - 2018

Start

2018-05-11 17:00 UTC

5 Maratona NexTI - 2018

End

2018-05-14 17:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -341 days 23:16:37

Time elapsed

72:00:00

Time remaining

0:00:00

Problem H
Prva

Little Ivica solves crossword puzzles every day. In case you haven’t seen one, a crossword puzzle starts on a grid of $R \times C$ squares, each of which is either empty or blocked. The player’s task is to write words in consecutive empty squares vertically (top down) or horizontally (left to right).

Ivica’s sister has a strange habit of looking at crosswords Ivica has finished solving, and finding the lexicographically smallest word in it. She only considers words at least $2$ characters long.

Write a program that, given a crossword puzzle, finds that word.

Input

The first line contains two integers $R$ and $C$ ($2 \le R, C \le 20$), the number of rows and columns in the crosswords.

Each of the following $R$ lines contains a string of $C$ characters. Each of those characters is either a lowercase letter of the English alphabet, or the character ‘#’ representing a blocked square.

The input will be such that a solution will always exist.

Output

Output the lexicographically smallest word in the crossword.

Sample Input 1 Sample Output 1
4 4
luka
o#a#
kula
i#a#
kala
Sample Input 2 Sample Output 2
4 4
luka
o#a#
kula
i#as
as
Sample Input 3 Sample Output 3
4 5
adaca
da##b
abb#b
abbac
abb