Problem Description

Given a character matrix of size $n \times m$, some positions are obstacles (denoted by the character #). You need to find a path starting from any point on the matrix (a cell can be revisited) such that the lexicographical order is maximized.

It can be proven that the answer is either finite or is obtained by repeating a finite-length string $S$. If the answer is finite, output it directly; if the answer is infinite, output its shortest repeating unit.

Input Format

The first line contains two positive integers $n$ and $m$.

The next $n$ lines, each containing a string of length $m$, describe the $n$-th row of the matrix.

Output Format

A single line containing a string representing the answer.

Sample Input and Output

Sample Input #1

3 3
###
#A#
###

Sample Output #1

A

Sample Input #2

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

Sample Output #2

BA

Sample Input #3

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

Sample Output #3

A

Notes

This problem uses batched testing.

Data Range:
- Subtask 1 (20pts): The character matrix contains only letters A and obstacles.
- Subtask 2 (30pts): $n, m \le 3$.
- Subtask 3 (50pts): No special restrictions.

For all data, $1 \le n, m \le 10^3$, all non-obstacle characters are uppercase letters, and the matrix contains at least one non-obstacle cell.

见题面 Input 部分

见题面 Output 部分