You are given a rectangular grid of lowercase letters and a target word. Starting from any cell, you may move to an orthogonally adjacent cell (up, down, left, or right — never diagonally), and you may never revisit a cell already used earlier in the same trace. Determine whether there exists some sequence of moves that spells out the target word exactly, one letter per visited cell in order.
Input format
Line 1: two integers rows and cols.
Next rows lines: each a string of exactly cols lowercase letters — one row of the grid.
Last line: the target word (a non-empty string of lowercase letters).
Output format
Print 1 if the word can be traced, otherwise print 0.
Constraints
- 1 ≤ rows, cols ≤ 6
- 1 ≤ length of word ≤ 8
- The grid contains only lowercase English letters.