Word Search in a Grid

You are given a grid of characters and a word. Your task is to determine if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are those immediately above, below, left, or right of the current cell. The same letter cell cannot be used more than once per search.

More formally, given a grid \(G\) of dimensions \(m \times n\) with characters and a string \(word\), you need to check if there is a path in \(G\) that spells out the \(word\). Use a depth-first search (DFS) with backtracking to explore all possible paths. The solution must read the input from stdin and write the result to stdout as either True or False.

Input Format: The first line contains two integers \(m\) and \(n\) indicating the number of rows and columns. The next \(m\) lines each contain \(n\) characters separated by spaces, representing the grid. The final line contains the word to be searched.

Output Format: A single line output printing True if the word exists in the grid, or False if it does not.

inputFormat

The input is given in the following format from stdin:

m n
row1_element1 row1_element2 ... row1_elementn
row2_element1 row2_element2 ... row2_elementn
...
rowm_element1 rowm_element2 ... rowm_elementn
word

For example:

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

outputFormat

The output is a single line printed to stdout containing either True or False, depending on whether the word exists in the grid.

## sample

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

True