Alien Keyboard Word Typing

You are given a keyboard layout of an alien language in the form of an n x m grid of lowercase letters. A word can be typed on this keyboard if, starting from any occurrence of its first character, you can traverse the grid by moving to one of the adjacent keys (including diagonals) for each subsequent character in the word.

Formally, if a key is located at position \((i,j)\), its neighbors are all keys at positions \((i+dx, j+dy)\) for \(dx,dy \in \{-1,0,1\}\) where not both \(dx\) and \(dy\) are zero. You cannot use the same key more than once in the same word path.

Determine whether the given word can be formed by traversing adjacent keys.

inputFormat

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

1. The first line contains two integers \(n\) and \(m\), the number of rows and columns of the keyboard.
2. The next \(n\) lines each contain a string of exactly \(m\) lowercase letters, representing a row of the keyboard.
3. The last line contains a string, representing the word to be checked.

outputFormat

Output a single line to standard output containing YES if the word can be typed following the above rules, or NO otherwise.

Two keys are considered adjacent if they are next to each other vertically, horizontally, or diagonally. In other words, from a key at \((i,j)\), you may move to any of the 8 neighbors \((i+dx, j+dy)\) where \(dx,dy \in \{-1,0,1\}\) and \((dx,dy) \neq (0,0)\).

4 5
abcde
fghij
klmno
pqrst
hello

NO