Description

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.

Input Format

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 Format

Output a single string representing the answer.

3 3
###
#A#
###

A

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

BA

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

A

Hint

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