Word Search in a Grid

You are given a $M \times N$ grid of uppercase English letters and a target word. The goal 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. Note that the same cell may not be used more than once in the construction of the word.

For example, given the grid:

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

and the word ABCCED, the answer is True. However, for the word ABCB, the answer is False.

Your task is to implement this functionality such that the program reads the grid and the word from standard input and writes the result to standard output.

inputFormat

The input is read from standard input in the following format:

1. The first line contains two integers M and N separated by a space, representing the number of rows and columns of the grid respectively.
2. The next M lines each contain a string of length N, representing the rows of the grid.
3. The last line contains a single string, which is the word to search for in the grid.

outputFormat

Output a single line to standard output: True if the word exists in the grid, otherwise False.## sample

3 4
ABCE
SFCS
ADEE
ABCCED

True