Longest Word in a Grid

You are given an \( m \times n \) grid of alphabetic characters. You can form a word by starting at any cell and moving to one of its adjacent cells. Two cells are considered adjacent if they share a side or a corner (i.e. 8 possible directions). Each cell may be used only once in the formation of a word.

Your goal is to find the longest word possible. The length of the longest word is \( m \times n \) if all cells are visited. If there are multiple answers with maximum length, you may output any one of them.

Note: The grid is provided as a 2D array of characters. Movement directions are up, down, left, right, and the four diagonals.

inputFormat

The input is read from standard input. The first line contains two positive integers (m) and (n) representing the number of rows and columns respectively. Each of the following (m) lines contains (n) characters separated by spaces, representing the grid.

outputFormat

Output a single line to standard output containing the longest word that can be formed. If more than one longest word exists, any one of them is acceptable.## sample

2 2
a b
c d

acdb