Word Search in a Grid

You are given a grid of characters with r rows and c columns, along with a target word. Your task is to determine whether the word exists in the grid by following one of the four allowed movement rules: moving horizontally (left or right) or vertically (up or down). The word must be matched sequentially in one of these directions. In other words, if the word has length n and you start at position (x, y) in the grid, then for a chosen direction specified by increments \(d_x\) and \(d_y\), the following conditions must hold for all \(i\) from 0 to \(n-1\):

\[ 0 \leq x + i \times d_x < r \quad \text{and} \quad 0 \leq y + i \times d_y < c \]

If any such sequence exists, output YES; otherwise, output NO.

inputFormat

The input is given via standard input (stdin) and consists of:

• A line with two integers \(r\) and \(c\), representing the number of rows and columns of the grid respectively.
• Next \(r\) lines, each containing a string of exactly \(c\) characters representing a row of the grid.
• A final line containing the target word to search for.

outputFormat

Print a single line to standard output (stdout). Output YES if the word is found in the grid according to the specified movement rules, otherwise output NO.

5 5
HELLO
WORLD
ABCDE
FGHIJ
KLMNO
HELLO

YES