Word Search in a 2D Grid

Given a 2D grid of characters and a target word, determine if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. Each cell can be used at most once.

Formally, let the grid be a matrix \(G\) of size \(m \times n\) and a word \(w\) of length \(k\). We want to find if there exists a path \(p_1, p_2, \ldots, p_k\) in the grid such that for each \(1 \le i < k\), \(p_{i+1}\) is adjacent to \(p_i\), and \(G(p_i) = w_i\). Note that the same cell cannot be used more than once.

For example, consider the grid:

A B C E
S F C S
A D E E

and the word "ABCCED". The word exists because a valid path can be found among adjacent cells.

inputFormat

The input is provided via standard input (stdin) in the following format:

m n
row1
row2
... 
row_m
word

Here, \(m\) and \(n\) are integers representing the number of rows and columns in the grid respectively. Each of the next \(m\) lines consists of a string with exactly \(n\) characters representing a row of the grid. The final line contains the word to search for in the grid.

outputFormat

Output to standard output (stdout) a single line containing True if the word exists in the grid; otherwise, output False.

## sample

3 4
ABCE
SFCS
ADEE
ABCCED

True

</p>