Migrated from Lutece 1708 数字串

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你有一个矩形，上面有一些（1-9）范围内的数字

你需要找一个路径，使路径上数字连成串后，数值最大

Input

多组数据，不超过 $30$ 组。

每组数据第一行是两个整数 $N,M$ 分别表示矩阵的行数和列数，$N,M \leq 30$，$N\times M \leq 30$。

之后是 $N$ 行，每行 $M$ 个字符，字符只有 1-9 与 # 十种情况，# 号表示此处不可通过。

如图所示，34863568 为一个可行的字符串，同样 34358 也是一种可能的字符串。题目要求一个数值最大的字符串。

输入数据以一行 0 0 结尾。

Output

最大的数值（数字字符串）

Samples

3 7
##9784#
##123##
##45###
0 0

791452384

Note

大力出奇迹，数据随机生成

Resources

2017 UESTC Training for Search Algorithm & String