Word Search on 2D Board

You are given a 2D board of characters and a target word. Your task is to determine if the word exists in the board. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are those horizontally or vertically neighboring. Each cell can be used only once in the construction of the word.

Note: The search must follow strict adjacency (only up, down, left, right moves are allowed) and the same cell cannot be reused in one search path.

Example:

Input:
3 4
A B C E
S F C S
A D E E
ABCCED
Output:
True

The board above gives rise to several possible search paths, but only one path properly constructs the word 'ABCCED'.

Additional Example: For the word "ABCB" in the same board, the output should be False because although the letters appear, the constraint of not reusing a cell is violated.

Your solution should read input from stdin and write the result to stdout.

inputFormat

The first line of the input contains two integers m and n representing the number of rows and columns of the board, respectively.

The following m lines each contain n uppercase letters (each separated by a space) representing the rows of the board.

The last line of the input contains a string representing the target word to search for in the board.

Example:

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

outputFormat

Output a single line with either True if the word exists in the board, or False if it does not.

Example:

True

## sample

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

True