Matrix Word Tracing

In this problem, you are given a 2D matrix of lowercase letters and a word. You need to determine if the word can be traced in the matrix. The word can be formed by moving to any of the 8 adjacent cells (horizontally, vertically, or diagonally) without reusing any cell.

The movement rules are:

• Horizontal: left and right
• Vertical: up and down
• Diagonal: all four diagonal directions

You may start from any cell in the matrix. If it is possible to form the word by consecutively connecting letters according to these rules, print YES; otherwise, print NO.

The underlying algorithm involves backtracking (depth-first search). Further, note that each cell may be used at most once for a given word trace.

The mathematical condition for movement (in LaTeX) can be summarized as: $$ (i',j') = (i+\Delta i,j+\Delta j), \quad \Delta i,\Delta j \in \{-1, 0, 1\}, \quad (\Delta i,\Delta j) \neq (0,0) $$

inputFormat

Input is read from stdin. The first line contains an integer T denoting the number of test cases. Each test case is structured as follows:

• The first line contains two integers n and m, representing the number of rows and columns of the matrix.
• The next n lines each contain a string of m lowercase letters (with no spaces), representing the matrix rows.
• The last line contains a string, which is the word to be traced in the matrix.

outputFormat

For each test case, output on a separate line YES if the word can be traced according to the rules, or NO otherwise. The output is printed to stdout.## sample

3
3 4
abcd
mnpq
xzyw
abc
4 4
abce
sfcs
adee
fsaf
see
3 3
abc
def
ghi
xyz

YES
YES
NO

</p>