Word Search in a Matrix

Problem Description:

Given an \(r \times c\) matrix consisting of uppercase English letters and a word, determine if the word exists in the matrix. A word can be constructed from letters of sequentially adjacent cells, where adjacent cells are those that are horizontally or vertically neighboring. Each cell may be used at most once in constructing the word.

For example, consider the matrix:

A B C E
S F C S
A D E E

and the word ABCCED, the output should be YES.

Your task is to write a program that reads the matrix and the word from standard input and outputs YES if the word exists in the matrix, otherwise outputs NO.

inputFormat

Input Format:

The first line contains two integers r and c denoting the number of rows and columns respectively. The next r lines each contain a string of length c representing the matrix, where each character is an uppercase letter. The last line contains the word to search for.

All the input is given via stdin.

outputFormat

Output Format:

Output a single line: YES if the word exists in the matrix, and NO otherwise. Write the output to stdout.

## sample

3 4
ABCE
SFCS
ADEE
ABCCED

YES