Problem Description

Given a crossword puzzle consisting of a matrix of symbols with dimensions $r \times c$, composed of lowercase letters and #.

A word is defined as a sequence of letters that are connected either horizontally or vertically in the matrix (excluding #), with a minimum length of 2. For vertical words, the top and bottom must either be bounded by # or the edge of the matrix; similarly, horizontal words must meet this requirement on the left and right sides.

Find the lexicographically smallest word.

Input Format

The first line contains two integers $r$ and $c$, representing the number of rows and columns of the matrix.

The following $r$ lines, each containing $c$ characters, describe the matrix.

Output Format

Output a single line containing the lexicographically smallest word.

Sample Input and Output

Sample Input #1

4 4
luka
o#a#
kula
i#a#

Sample Output #1

kala

Sample Input #2

4 4
luka
o#a#
kula
i#as

Sample Output #2

as

Sample Input #3

4 5
adaca
da##b
abb#b
abbac

Sample Output #3

abb

Notes

Data Constraints

For $100\%$ of the data, it is guaranteed that $2 \le r, c \le 20$.

Notes

This problem is translated from COCI2007-2008 CONTEST #2 T3 PRVA.

见题面 Input 部分

见题面 Output 部分