Lexicographically Maximum Path in a Grid

Given an \(n\times m\) grid of characters where some positions contain obstacles (represented by the character #), find a path on the grid such that the concatenated string along the path is lexicographically maximum. The path may start at any cell and is allowed to revisit cells.

It can be proven that the answer is either a finite string or an infinite string, which can be expressed as an infinite repetition of a finite string \(S\). If the answer is finite, output the string directly; if it is infinite, output its shortest repeating segment, i.e. the minimal \(S\) in LaTeX format.

For the purpose of this problem, assume that you can move from a cell to any of its four adjacent cells (up, down, left, right) as long as the move is within bounds. Note that you cannot move into an obstacle cell.

inputFormat

The first line contains two integers \(n\) and \(m\) which denote the number of rows and columns in the grid.

This is followed by \(n\) lines, each containing a string of length \(m\). Each character in the string is either an uppercase or lowercase letter or the character # indicating an obstacle.

outputFormat

If the lexicographically maximum string is finite, output it directly. Otherwise, if the answer is infinite, output the shortest repeating segment \(S\) (in \(\LaTeX\) format) that, when repeated, yields the infinite string.

sample

3 3
abc
d#e
fgh

h