Word Search

Problem statement

A word trail puzzle lays letter tiles in a rectangular board. A player spells a word by walking between tiles that share an edge, but each tile can be used only once during that attempt. Your task Determine whether the target word can be formed by a path of horizontally or vertically adjacent cells. The first letter may start anywhere on the board. Important details Diagonal steps are forbidden. Two cells with the same letter remain different tiles, but revisiting the same cell is forbidden. The path need not be straight, and letter comparisons are case-sensitive. Worked example On the board with rows AB and CD, the path A -> B -> D spells ABD. The cells share edges consecutively, so the answer is true.

Input format

First line: rows columns. Next rows lines: board strings without spaces. Final line: word.

Output format

Print true if the condition holds, otherwise false.

Constraints

1 <= rows, columns <= 6; 1 <= word length <= 15; board and word contain English letters.

Sample input

2 2
AB
CD
ABD

Sample output

true