Lexicographically Smallest Crossword Word

Interview

Time limit1sMemory limit128 MB

Summary

Extract all horizontal and vertical maximal letter sequences of length at least 2 from a grid and output the lexicographically smallest one.

Level: Easy3 of 10
Topics: String, Implementation, Simulation
Solved: No attempts yet

Problem

A crossword is an R x C rectangular grid. Each cell contains either a lowercase English letter or #, and # means the cell is blocked.

A word is a maximal consecutive sequence of unblocked cells read left to right in a row or top to bottom in a column. Only sequences of length at least 2 are words.

Given a filled crossword, print the lexicographically smallest word that appears in the grid.

Input

The first line contains two integers R and C (2 <= R, C <= 20), the number of rows and columns.

Each of the next R lines contains C characters. Every character is either a lowercase English letter or #. A # character represents a blocked cell.

Output

Print the lexicographically smallest word on one line.

The input is guaranteed to contain at least one valid word.

Examples3

Example 1
Input
```
4 4
luka
o#a#
kula
i#a#
```
Expected output
```
kala
```
Example 2
Input
```
4 4
luka
o#a#
kula
i#as
```
Expected output
```
as
```
Example 3
Input
```
4 5
adaca
da##b
abb#b
abbac
```
Expected output
```
abb
```