Word Search Puzzle

You are given a grid of characters and a target word. Your task is to determine whether the word exists in the grid by constructing it from letters of sequentially adjacent cells. Two cells are considered adjacent if they are horizontally or vertically neighboring. Each cell can be used only once in the construction of the word.

Formally, given a grid \(G\) of size \(R \times C\) and a word \(W\), check if there exists a path in \(G\) such that the concatenation of letters along the path equals \(W\). The movement is restricted to up, down, left, or right moves. If such a path exists, output YES, otherwise output NO.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers (R) and (C), representing the number of rows and columns in the grid.
• The next (R) lines each contain a string of length (C) representing a grid row. Note that if (C = 0), the corresponding line will be empty.
• The last line contains the target word (W).

For example:

3 4 abce sfcs adee abcced

outputFormat

Output to standard output (stdout) a single line containing either YES if the word exists in the grid, or NO if it does not.## sample

3 4
abce
sfcs
adee
abcced

YES