Word Search in Grid

You are given a grid of characters with R rows and C columns and a list of N words. Your task is to determine for each word whether it exists in the grid. A word is said to exist if its letters can be connected sequentially using adjacent cells (horizontally or vertically). Moreover, the same cell cannot be used more than once in forming a single word.

In mathematical terms, for a given word \(w\) of length \(L\), you need to find a sequence of coordinates \((i_1,j_1), (i_2,j_2), \ldots, (i_L,j_L)\) in the grid such that:

[ \begin{aligned} & grid[i_k][j_k] = w_k, \quad 1 \le k \le L, \ & \text{and} \quad |i_k - i_{k+1}| + |j_k - j_{k+1}| = 1, \quad 1 \le k < L, \ & (i_x,j_x) \neq (i_y,j_y) \quad \text{for all } x \neq y. \end{aligned} ]

If such a sequence exists, then the answer for that word is True; otherwise, it is False.

inputFormat

The input is read from standard input (stdin) and has the following format:

R C
row1
row2
... 
rowR
N
word1
word2
... 
wordN

Where:

• R and C are two integers representing the number of rows and columns of the grid.
• Each of the next R lines is a string of length C representing a row in the grid.
• N is the number of words to search.
• Each of the next N lines contains a word.

outputFormat

For each word provided in the input, output a single line containing True if the word can be found in the grid according to the rules above, or False if it cannot.

## sample

3 4
ABCE
SFCS
ADEE
3
ABCCED
SEE
ABCB

True
True
False

</p>