Word Search in a Grid

Given a grid of characters of size \(R \times C\) and a target word, determine if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells (adjacent means horizontally, vertically, or diagonally neighboring). Each cell may only be used once in the construction.

For example, consider the following grid:

A B C E
S F C S
A D E E

The word \(ABCCED\) is present in the grid, while the word \(ABCB\) is not.

inputFormat

The first line contains two integers, \(R\) and \(C\), representing the number of rows and columns of the grid. If both \(R\) and \(C\) are zero, the grid is empty.

If \(R\) and \(C\) are greater than zero, the next \(R\) lines each contain \(C\) space-separated uppercase characters that represent the grid.

The final line contains the target word to search for. Note that the word may be empty.

outputFormat

Output a single line: True if the word can be constructed in the grid following the rules, or False otherwise.

## sample

3 4
A B C E
S F C S
A D E E
ABCCED

True

</p>