Word Search on Grid

You are given a 2D board of characters and a list of words. Your task is to find all the words from the list that can be constructed from the board. A word can be constructed from letters of sequentially adjacent cells, where adjacent cells are those horizontally or vertically neighboring. Note that the same cell cannot be used more than once in a single word.

The problem can be formulated using a trie (prefix tree) to optimize the search for words. You may assume the board dimensions and the word list are such that a solution using backtracking with a trie is efficient. In particular, if a word is found, it should be printed exactly once.

Mathematical Formulation: For a board with dimensions \( m \times n \) and a word \( w \) of length \( k \), we must check if there exists a sequence of coordinates \( (i_1, j_1), (i_2, j_2), \dots, (i_k, j_k) \) such that:

[ \begin{aligned} & w[\ell] = board[i_{\ell}][j_{\ell}] \quad \text{for } 1 \leq \ell \leq k, \[6pt] & |i_{\ell} - i_{\ell+1}| + |j_{\ell} - j_{\ell+1}| = 1, \quad \text{for } 1 \leq \ell < k, \[6pt] & \text{and } (i_p, j_p) \neq (i_q, j_q) \quad \text{for all } p \neq q. \end{aligned} ]

inputFormat

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

1. The first line contains two integers \( R \) and \( C \) which represent the number of rows and columns of the board. If both are 0, the board is empty.
2. The next \( R \) lines each contain \( C \) characters separated by spaces representing the board.
3. The following line contains an integer \( N \) which is the number of words.
4. The next \( N \) lines each contain a word.

All input is provided via stdin.

outputFormat

Output the list of found words in lexicographically sorted order in a single line, separated by a space. If no words are found, output an empty line. The output should be sent to stdout.

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