AT_past17_g 蛇行する文字列

There is a grid with $ H $ horizontal rows and $ W $ vertical columns. We denote by $ (i,j) $ the cell in the $ i $ -th row from the top and $ j $ -th column from the left. Each cell has a lowercase English letter written on it. The letter written on $ (i, j) $ is $ G_{i, j} $ . You are given a string $ S $ of length $ N $ . Is there a sequence of cells $ (a_1, b_1) $ , $ (a_2, b_2) $ , $ \dots $ , $ (a_N, b_N) $ that satisfies the following conditions? Print `Yes` if there is, and `No` otherwise. - $ (a_1, b_1) $ , $ (a_2, b_2) $ , $ \dots $ , and $ (a_N, b_N) $ are pairwise distinct. - $ (a_i, b_i) $ and $ (a_{i+1}, b_{i+1}) $ are adjacent in one of the eight directions. In other words, $ \max(\vert a_i - a_{i+1} \vert, \vert b_i - b_{i+1} \vert) = 1 $ . - The letter written on $ (a_i, b_i) $ coincides with the $ i $ -th character of $ S $ .

The input is given from Standard Input in the following format: > $ H $ $ W $ $ G_{1,1}G_{1,2}\dots G_{1,W} $ $ G_{2,1}G_{2,2}\dots G_{2,W} $ $ \vdots $ $ G_{H,1}G_{H,2}\dots G_{H,W} $ $ N $ $ S $

Print `Yes` if there is a conforming sequence of cells; print `No` otherwise.

### Sample Explanation 1 The sequence of cells $ (2, 1), (3, 2), (2, 3), (1, 2), (1, 1) $ satisfies all the conditions in the problem statement, so the answer is `Yes`. ### Constraints - $ 1 \leq H, W \leq 10 $ - $ G_{i, j} $ is a lowercase English letter. - $ 1 \leq N \leq 5 $ - $ S $ is a length- $ N $ string consisting of lowercase English letters.