Word Search in a Grid

You are given an N×M grid of uppercase English letters 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 horizontally or vertically neighboring. Each cell can be used only once for each word search.

More formally, let the grid be represented by \(G\) and the target word by \(W\). You need to check if there exists a sequence of coordinates \((i_1, j_1), (i_2, j_2), \dots, (i_k, j_k)\) such that:

• \(G_{i_1,j_1} = W_1, G_{i_2,j_2} = W_2, \dots, G_{i_k,j_k} = W_k\),
• For every \(1 \leq t < k\), \( (i_t, j_t) \) and \( (i_{t+1}, j_{t+1}) \) are adjacent (i.e., share a side),
• No cell is used more than once in constructing the word.

If such a sequence exists, output True; otherwise, output False.

inputFormat

The input is given from standard input (stdin) in the following format:

The first line contains two integers (N) and (M), denoting the number of rows and columns in the grid, respectively.

The next (N) lines each contain a string of exactly (M) uppercase letters, representing a row of the grid.

The last line contains a string representing the target word to search for in the grid.

outputFormat

Output a single line to standard output (stdout):

Print True if the word exists in the grid according to the defined conditions, or False otherwise.## sample

3 4
ABCE
SFCS
ADEE
ABCCED

True