题目描述

给定一个 $r\times c$ 的符号方阵组成的填词游戏，里面由小写字母和 # 组成。

一个单词指的是在方阵中从左到右或从上到下把经过的字母依次相连（不得包含 #）形成的字母串。不一定要整行或整列都包含，且这个字母串的长度至少为 $2$。对于竖向的单词，头尾的上方或者下方要么顶着 #，要么处于边界；横向单词的左右也需要符合这个要求。

请你求出字典序最小的单词。

输入格式

输入第一行为两个整数 $r,c$，表示方阵的行数和列数。

接下来的 $r$ 行，每行 $c$ 个字符，描述这个方阵。

输出格式

输出一行若干个字母，表示字典序最小的单词。

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

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $2\le r,c\le 20$。

说明

题目译自 COCI2007-2008 CONTEST #2 T3 PRVA。