Word Search in a Grid

You are given a 2D grid of characters of size \(m \times n\) and a target word. The 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 may only be used once in the construction of the word.

Example:

Input:
3 4
ABCE
SFCS
ADEE
ABCCED
Output:
true

</p>

In the above example, the word "ABCCED" can be found along a valid path in the grid.

Note: The word search is case-sensitive and the grid will contain only uppercase letters.

inputFormat

The input is read from stdin and is formatted as follows:

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

All input values are separated by newlines.

outputFormat

Print a single line to stdout: true if the word exists in the grid, and false otherwise.

## sample

3 4
ABCE
SFCS
ADEE
ABCCED

true