Word Search in a Grid

You are given a 2D grid of characters and a word. Your task is to determine whether the given word can be constructed from letters of sequentially adjacent cells in the grid. Cells are considered adjacent if they are immediately left, right, up, or down. Each cell can be used at most once.

More formally, given a grid G of dimensions \(r \times c\) and a word \(W\), check if there exists a sequence of coordinates \((i_1,j_1), (i_2,j_2), \dots, (i_k,j_k)\) such that:

• For every \(l\) with \(1 \le l \le k\), \(G[i_l][j_l] = W[l-1]\).
• For every consecutive pair \((i_l,j_l)\) and \((i_{l+1},j_{l+1})\), they are adjacent (up, down, left, or right).
• No cell is used more than once.

If such a sequence exists, print YES; otherwise, print NO.

Note: The empty word is considered to be found in any grid.

inputFormat

The input is given from stdin in the following format:

r c
A1 A2 ... Ac
... (r lines total)
word

Where:

• r and c are two integers representing the number of rows and columns respectively. If r is 0, the grid is empty.
• The next r lines each contain c characters separated by spaces, representing the grid.
• The last line contains the word to search. Note that the word can be empty.

outputFormat

Output a single line to stdout with either YES if the word can be found in the grid following the rules, or NO otherwise.

## sample

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

YES

</p>