Word Search Puzzle

Given a matrix of characters and a word, determine if the word exists in the matrix. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. A cell cannot be used more than once in a single word search.

Note: The search is case-sensitive.

Example:

Input:
3 4
ABCE
SFCS
ADEE
ABCCED
Output:
True

</p>

In the above example, the board is a 3x4 matrix and the word "ABCCED" exists in the matrix following a valid path.

inputFormat

The input is provided via standard input (stdin) in the following format:

R C
row1
row2
...
rowR
word

Where R and C are the number of rows and columns in the matrix respectively. Each of the next R lines contains a string of exactly C characters (without spaces) representing the matrix row. The last line contains the word to search in the matrix.

outputFormat

The output should be printed to standard output (stdout) as either "True" if the word exists in the board or "False" if it does not.

## sample

3 4
ABCE
SFCS
ADEE
ABCCED

True