题目描述

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

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

输入格式

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

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

输出格式

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

3 3
###
#A#
###

A

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

BA

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

A

提示

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