Word Search in a 2D Grid

Given an m x n grid of characters, determine if a given 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. You may not use the same cell more than once.

Formally, given the grid \(board\) and a string \(word\), check if there exists a path in the grid that spells out the \(word\). The path can start at any cell and move in one of four directions: up, down, left, or right.

For example, consider the grid:

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

The word ABCCED can be found following the path: (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,1), thus the answer is True.

inputFormat

The input is given via standard input (stdin). The first line contains two space-separated integers m and n representing the number of rows and columns in the board.

The next m lines each contain a string of length n representing a row of the board.

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

outputFormat

Output a single line to standard output (stdout) containing either "True" if the word exists in the board following the adjacent cell rule, or "False" otherwise.

## sample

3 4
ABCE
SFCS
ADEE
ABCCED

True