P10677 『STA - R6』inkar-usi

 (The background image is from the Arcaea song artwork. If there are any copyright issues, please contact the problem author.)

Given an $n \times m$ character matrix where some positions are obstacles (denoted as `#`), find a path starting from any cell (revisiting cells is allowed) such that its lexicographical order is maximized. It can be proven that the answer is either finite or formed by infinite repetitions of a finite string $S$. If the answer is finite, output it directly. If the answer is infinite, output its shortest repeating cycle.

The first line contains two positive integers $n$ and $m$. The next $n$ lines each contain a string of length $m$, describing the corresponding row of the matrix.

Output a single string representing the answer.

**This problem uses subtask scoring.** Data Constraints: - Subtask 1 (20 points): All non-obstacle characters in the matrix are `A`. - Subtask 2 (30 points): $n, m \le 3$. - Subtask 3 (50 points): No additional constraints. For all test cases, $1 \le n, m \le 10^3$, all non-obstacle characters are uppercase letters, and the matrix contains at least one non-obstacle cell. Translation by DeepSeek R1