Word Search in a Grid

You are given a 2D grid of characters and a target word. Your task is to determine whether the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are those that are directly horizontal or vertical neighbors. Note that the same cell cannot be used more than once in the construction of the word.

The search process can be understood with the following recursive relation:

[ DFS(i,j,k) = \begin{cases} True & \text{if } k = |word| \ False & \text{if } i < 0 \text{ or } i \ge m \text{ or } j < 0 \text{ or } j \ge n \text{ or } grid[i][j] \neq word[k] \ DFS(i+1,j,k+1) \lor DFS(i-1,j,k+1) \lor DFS(i,j+1,k+1) \lor DFS(i,j-1,k+1) & \text{otherwise} \end{cases} ]

If any path returns true then the word exists in the grid; otherwise, it does not.

For example:

Input:
3 4
ABCE
SFCS
ADEE
ABCCED
Output:
True

</p>

inputFormat

The input is given from stdin with the following format:

• The first line contains two integers m and n representing the number of rows and columns of the grid, respectively.
• The next m lines each contain a string of length n representing a row of the grid.
• The last line contains the target word to search for.

outputFormat

Output a single line to stdout containing either True if the word exists in the grid, or False otherwise.

## sample

1 4
ABCE
ABC

True