크로스워드

동혁이는 크로스워드 퍼즐을 좋아한다. R x C 크기의 완성된 크로스워드 퍼즐이 주어진다. 각 칸에는 알파벳 소문자 하나가 들어 있거나, 단어가 들어갈 수 없는 칸을 나타내는 #이 들어 있다.

퍼즐에서 단어는 가로 또는 세로 방향으로 연속한 두 글자 이상의 알파벳으로 이루어진다. 단어의 양끝은 퍼즐의 경계이거나 #이어야 하므로, 같은 방향으로 더 길게 확장할 수 없어야 한다.

퍼즐에 있는 모든 단어 중 사전순으로 가장 앞서는 단어를 구하시오.

첫째 줄에 퍼즐의 행 수 R과 열 수 C가 공백으로 구분되어 주어진다. (2 <= R, C <= 20)

다음 R개의 줄에는 완성된 퍼즐이 주어진다. 각 줄은 알파벳 소문자 또는 금지된 칸을 나타내는 #으로 이루어진 길이 C의 문자열이다.

입력에는 단어가 하나 이상 존재한다.

퍼즐에 있는 단어 중 사전순으로 가장 앞서는 단어를 한 줄에 출력한다.