Lexicographically Smallest Crossword Word

You are given a crossword puzzle grid of size \(r \times c\) composed of lowercase letters and the character '#' representing a blocked cell.

A word is defined as a contiguous sequence of letters (i.e. characters that are not '#') read either horizontally from left to right or vertically from top to bottom. The word must have a length of at least \(2\) characters. In addition, the following boundary conditions must be satisfied:

• For a horizontal word, the cell immediately to the left of the first letter (if it exists) and the cell immediately to the right of the last letter (if it exists) must either be '#' or lie on the boundary of the grid.
• For a vertical word, the cell immediately above the first letter (if it exists) and the cell immediately below the last letter (if it exists) must either be '#' or lie on the boundary of the grid.

Your task is to find and output the lexicographically smallest valid word in the grid.

inputFormat

The first line contains two integers \(r\) and \(c\) separated by a space, representing the number of rows and columns, respectively.\nbsp;

Each of the following \(r\) lines contains a string of length \(c\) consisting of lowercase letters and '#' characters representing one row of the grid.

outputFormat

Output the lexicographically smallest valid word found in the crossword puzzle.

sample

4 4
luka
o#a#
kano
teet

ae