F. Maze Runner
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
A contest without a grid is like Mansaf without meat
— Hungry Abd and Ahmad, Midnight Diaries

Mateo and Juan are trapped in a maze, and they can only escape the maze if they draw a certain pattern on it, so they are desperate for your help!

The maze is represented as a grid $$$G$$$ of size $$$n \times m$$$, each cell is a lowercase English letter, you can move from a cell to any other cell adjacent to it (diagonally, horizontally and vertically), you can visit the cell more than once, but you can't move to the same cell that you are currently on.

Let's define a pattern of a path as the concatenation of the characters on the cells on that path.

In a more formal way let the cells on the path be $$$P = [(r_1, c_1), (r_2, c_2), ..., (r_k, c_k)]$$$ such that for each $$$2 \leq i \leq k$$$ $$$P_i \neq P_{i - 1}$$$ that then the pattern is $$$S = G_{r_1c_1}G_{r_2c_2}...G_{r_kc_k}$$$.

Mateo and Juan are studying $$$q$$$ patterns, for each one they ask you if they can draw that pattern on the maze.

Input

The first line contains two integers $$$n$$$ $$$(1 \leq n \leq 10)$$$ and $$$m$$$ $$$(1 \leq m \leq 10)$$$.

For the next $$$n$$$ lines, each line contains $$$m$$$ characters the $$$j_{th}$$$ character on the $$$i_{th}$$$ line describes the cell $$$G_{ij}$$$.

The next line contains one integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$.

For the next $$$q$$$ lines, each line contains a pattern $$$S$$$ $$$(1 \leq |S| \leq 13)$$$.

Output

For each of the $$$q$$$ patterns, print "YES" if it can be drawn on the grid, otherwise "NO".

Examples
Input
2 2
ab
ju
4
auabj
auau
jbjbjbjb
ajbuabu
Output
YES
YES
YES
YES
Input
10 10
mpflatybop
qidzzqtjqx
doqoqpytaw
dmoiaobarq
qhatjzlcke
cpssejhcck
bfypoyfrbw
jrfkmqlxtw
bxluprfzuh
jxphofitwj
4
ssejh
sseja
bxxjbxx
bxxlkpfoo
Output
YES
YES
YES
NO