『STA - R6』inkar-usi
题目背景
（题目背景图片来自 Arcaea 曲绘，如有侵权，请告知出题人。）
题目描述
给一个 $n\times m$ 的字符矩阵，有些位置有障碍（记为字符 `#`），需要在矩阵上找出一条起始点任意的路径（可以重复经过某个格子），使得字典序最大。
可以证明答案一定是有限的或者是由某个长度有限的字符串 $S$ 不断重复得到的。如果答案是有限的，直接输出之；如果答案是无限的，只需输出它的最短循环节。
输入输出格式
输入格式
第一行两个正整数 $n,m$。
后 $n$ 行，每行一个长度为 $m$ 的字符串，描述矩阵的第 $n$ 行。
输出格式
一行一个字符串，表示答案。
输入输出样例
输入样例 #1
3 3
###
#A#
###输出样例 #1
A输入样例 #2
3 4
####
#AB#
####输出样例 #2
BA输入样例 #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$，所有非障碍字符都是大写字母，矩阵至少有一个非障碍格。