小 Greedy 在生日时收到了一个棋盘。棋盘有 $N$ 行 $M$ 列，每个格子里都有一个英文小写字母。在生日派对上，大家都觉得很无聊，于是决定玩一个简单的棋盘游戏。

游戏开始时，将一枚棋子放在坐标为 $(1, 1)$ 的左上角格子里。在每一步中，我们必须将棋子向右或向下移动一格，且必须保证棋子留在棋盘内。当棋子移动到坐标为 $(N, M)$ 的右下角格子时，游戏结束。在游戏过程中，我们记录下移动棋子时经过的字符序列，从而构造出一个单词。游戏的目标是找到字典序最小的单词。

成功拼出字典序最小单词的玩家将获得一袋糖果作为奖励。Greedy 无论如何都想赢得糖果，因此他请求你编写一个程序，来寻找可能拼出的字典序最小的单词。

请注意：单词的字典序就是它们在词典中出现的顺序。如果我们有两个单词，且它们在第一个不同的位置上字母不同，那么该位置字母在字母表中更靠前的单词更小。

输入格式

输入的第一行包含两个空格隔开的整数 $N$ 和 $M$（$1 \le N, M \le 2000$）。

接下来的 $N$ 行，每行包含 $M$ 个英文小写字母，表示棋盘。

输出格式

输出必须为可能拼出的字典序最小的单词。

子任务

在总分 40 分的测试数据中，对于每个格子，其右边和下边的字母均不相同。

样例

输入样例 1

4 5
ponoc
ohoho
hlepo
mirko

输出样例 1

pohlepko

输入样例 2

4 5
bbbbb
bbbbb
bbabb
bbbbb

输出样例 2

bbbbabbb

输入样例 3

2 5
qwert
yuiop

输出样例 3

qweiop

说明

第一个样例的解释：

构造最小单词的一种方式如下图所示：