Word Search in a Matrix

You are given a 2D grid (matrix) of uppercase English letters and a target word. Your task is to determine if the given word can be found in the grid by connecting sequentially adjacent cells. Two cells are considered adjacent if they are horizontally, vertically, or diagonally neighboring. Each letter cell may be used at most once in forming the word.

Formally, let \( board \) be a matrix of size \( R \times C \) and \( word \) a string. You need to determine if there exists a path in \( board \) such that the characters along the path form the word. The same cell may not be used more than once in the same path.

Note: The allowed moves include all 8 possible directions, i.e., up, down, left, right, and the four diagonal directions.

Example:

Input:
3 4
A B C E
S F C S
A D E E
ABCCED
Output:
YES

</p>

inputFormat

The input is read from standard input (stdin) in the following format:

1. The first line contains two integers \( R \) and \( C \), representing the number of rows and columns respectively.
2. The next \( R \) lines each contain \( C \) uppercase letters separated by spaces, representing the grid.
3. The last line contains a string, representing the target word to search for.

outputFormat

Output a single line to standard output (stdout): - Print YES if the word exists in the grid according to the rules, otherwise print NO.

## sample

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

YES