Word in a letter grid

Problem

A puzzle page shows a grid of capital letters. A word is in the grid if you can read it by starting at any cell and moving one cell up, down, left or right for each next letter, never using the same cell twice. Print YES if the word is in the grid and NO if it is not.

Input, output and limits

Input: Line 1: rows r and columns c. The next r lines: the grid, c letters each. The last line: the word.
Output: YES or NO.
Constraints: 1 ≤ r, c ≤ 4
1 ≤ length of the word ≤ 12

Examples

Example

Input

3 4
CATS
OREP
DENT
CORE

Output

YES

C, O, R, E move down, right and right.

Hints

Try the problem first. Open one hint at a time.

Hint 1

Start a search from every cell whose letter matches the first letter of the word.

Hint 2

While you are inside a cell, overwrite it with # so it cannot be used again, and put the letter back when you leave.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Python problems

Problem

Input, output and limits

Examples

Hints

More Backtracking problems

Problem

Input, output and limits

Examples

Hints

More Backtracking problems