Word Search in a Grid

You are given a 2D grid of characters and a list of words. Your task is to find all the words in the list that can be formed by sequentially adjacent letters in the grid, where adjacent means horizontally or vertically neighboring cells. Each letter cell may be used only once in forming a word. The found words must be output in lexicographical order.

Note: If a word cannot be found in the grid, it should not appear in the output.

The problem can be mathematically formalized as follows: Given a grid \(G\) of size \(m \times n\) and a set of words \(W = \{w_1, w_2, \ldots, w_k\}\), find the subset \(W' \subseteq W\) such that for each word \(w \in W'\), there exists a sequence of positions \((i_1, j_1), (i_2, j_2), \ldots, (i_{|w|}, j_{|w|})\) satisfying:

\(1 \leq i_p \leq m, \ 1 \leq j_p \leq n\) for all \(p\);

\(G[i_p][j_p] = w[p]\) for all \(p\);

For \(1 \leq p < |w|,\) the cells \((i_p, j_p)\) and \((i_{p+1}, j_{p+1})\) are adjacent (i.e. share a side);

Each cell is used at most once in forming any single word.

inputFormat

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

m n
row1
row2
...
row_m
k
word_1
word_2
...
word_k

Where:

• \(m\) and \(n\) are integers representing the number of rows and columns in the grid.
• Each of the next \(m\) lines contains \(n\) space-separated lowercase letters representing a row of the grid.
• \(k\) is an integer representing the number of words.
• Each of the following \(k\) lines contains a word.

outputFormat

The output should be printed to stdout as a single line containing the found words in lexicographical order, separated by a single space. If no words are found, output an empty line.

## sample

4 4
o a a n
e t a e
i h k r
i f l v
4
oath
pea
eat
rain

eat oath