Word Search in a Grid

Given a two-dimensional 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 (adjacent cells are those horizontally or vertically neighboring). Note that the same letter cell cannot be used more than once in a single search path.

Formally, let the grid be represented as (G) with dimensions (m \times n) and the target word be represented as (W = w_1w_2\ldots w_k). You need to check if there exists a sequence of cells ((i_1,j_1), (i_2,j_2),\ldots, (i_k,j_k)) such that for all (1 \leq t \leq k), (G[i_t][j_t] = w_t) and for every (1 \leq t < k), the cells ((i_t,j_t)) and ((i_{t+1},j_{t+1})) are adjacent.

If such a path exists, output true; otherwise, output false.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains two space-separated integers (m) and (n), representing the number of rows and columns of the grid.
2. The next (m) lines each contain (n) space-separated uppercase letters, representing the grid.
3. The last line contains the target word.

outputFormat

Output a single line to stdout containing true if the word exists in the grid, or false otherwise.## sample

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

true