Eugene's Boring Book Drawing

Eugene is reading a boring book but to entertain himself he draws on a piece of graph paper. Initially, all cells are empty. He first paints one cell, then starts reading. Whenever he sees one of the four letters u, d, l or r in the text he moves his pen one cell in the corresponding direction (up, down, left, right) and paints the new cell. (If a cell was painted before, he paints it again.)

You are given the drawing (a grid) and the text of the book. Determine whether the picture on the paper could have been drawn by Eugene by using some contiguous substring of the book text. In other words, after filtering the substring for only the four command letters, if we simulate the process starting from an arbitrary cell (which we take as coordinate \((0,0)\)) and apply each command (with:

• \(u\) decrements the row by 1,
• \(d\) increments the row by 1,
• \(l\) decrements the column by 1,
• \(r\) increments the column by 1),

we obtain a set of painted cells (the starting cell plus the cell after every move). Because the paper is infinite, the pattern is determined only up to translation. Thus after normalizing both the drawing and the simulated set (by subtracting the minimum row and column from every coordinate), they must match exactly. Note that the number of moves (\(L\)) in the effective command sequence must be one less than the number of painted cells in the drawing.

Input/Output details are given below.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \leq n,m \leq 50\)), the number of rows and columns of the drawing.

The following \(n\) lines each contain a string of length \(m\). Each character is either X (painted) or . (empty). It is guaranteed that there is at least one painted cell.

The last line contains a non-empty string representing the text of the book. The text consists of at most 1000 characters. The commands recognized by Eugene are the letters u, d, l, and r. Other characters are ignored. Note that Eugene may use some contiguous substring of the book text.

outputFormat

Output a single line: YES if it is possible that the drawing was created by Eugene using some contiguous substring of the text; otherwise, output NO.

sample

1 1
X
abc

YES