Word Search in Grid

You are given one or more grids of letters along with a target word for each grid. Your task is to determine whether the given word exists in the grid. The word can be formed from letters of sequentially adjacent cells, where adjacent cells are those that are horizontally or vertically neighboring.

Rules:

• You may not use the same cell more than once when constructing the word.
• The search is performed on each grid independently.
• Input ends when a grid with dimensions 0 0 is encountered (and this grid should not be processed).

Note: If desired, you may refer to the DFS (Depth-First Search) algorithm in your solution. In mathematical notation, if the grid is represented by an array \(G\) and the word is \(W = w_1w_2\dots w_k\), then a valid path \((i_1,j_1), (i_2,j_2), \ldots, (i_k,j_k)\) must satisfy:

[ \begin{aligned} G(i_1,j_1)&=w_1,\ G(i_2,j_2)&=w_2,\ &,\vdots\ G(i_k,j_k)&=w_k,\ \end{aligned} ]

and for each \(1 \leq p < k\), \((i_p, j_p)\) and \((i_{p+1}, j_{p+1})\) must be adjacent horizontally or vertically.

inputFormat

The first line of each test case contains two integers m and n representing the number of rows and columns of the grid, respectively. The next m lines contain n characters each (separated by spaces) representing the grid. The following line contains the target word.

The input may contain multiple test cases. The input terminates with a line containing "0 0", which should not be processed.

outputFormat

For each grid, output a single line containing Yes if the word can be found in the grid, or No otherwise.

## sample

3 4
a b c e
s f c s
a d e e
abcced
3 4
a b c e
s f c s
a d e e
see
2 2
a b
c d
abcd
0 0

Yes
Yes
No

</p>