Problem Description

You are given a crossword grid of symbols of size $r \times c$, consisting of lowercase letters and #.

A word is a string formed by connecting the letters encountered in the grid from left to right or from top to bottom in order (it must not contain #). It does not have to cover an entire row or column, and its length must be at least $2$. For a vertical word, the cell above its first letter and the cell below its last letter must either be # or be outside the grid boundary. For a horizontal word, the left of its first letter and the right of its last letter must satisfy the same condition.

Please output the lexicographically smallest word.

Input Format

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

The next $r$ lines each contain $c$ characters describing the grid.

Output Format

Output one line with some letters, representing the lexicographically smallest word.

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

kala

4 4
luka
o#a#
kula
i#as

as

4 5
adaca
da##b
abb#b
abbac

abb

Hint

Constraints

For $100\%$ of the testdata, $2 \le r, c \le 20$.

Note

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

Translated by ChatGPT 5