题目描述

给一个 $n\times m$ 的字符矩阵，有些位置有障碍（记为字符 #），需要在矩阵上找出一条起始点任意的路径（可以重复经过某个格子），使得字典序最大。

可以证明答案一定是有限的或者是由某个长度有限的字符串 $S$ 不断重复得到的。如果答案是有限的，直接输出之；如果答案是无限的，只需输出它的最短循环节。

输入格式

第一行两个正整数 $n,m$。

后 $n$ 行，每行一个长度为 $m$ 的字符串，描述矩阵的第 $n$ 行。

输出格式

一行一个字符串，表示答案。

样例 #1

样例输入 #1

3 3
###
#A#
###

样例输出 #1

A

样例 #2

样例输入 #2

3 4
####
#AB#
####

样例输出 #2

BA

样例 #3

样例输入 #3

3 4
####
#AA#
####

样例输出 #3

A

提示

数据范围：

• Subtask 1 (20pts)：字符矩阵中除了障碍就是字母 A。

• Subtask 2 (30pts)：$n,m\le 3$。

• Subtask 3 (50pts)：无特殊限制。

对于全部数据，$1\le n,m\le 10^3$，所有非障碍字符都是大写字母，矩阵至少有一个非障碍格。