Word Search in a Board

You are given an m x n board of characters and a dictionary of words. Your task is to find all words from the dictionary that can be formed in the board by connecting adjacent cells. Here, adjacent cells are those that share an edge or a corner, i.e. you can move in 8 directions: up, down, left, right, or diagonally.

A cell cannot be used more than once in forming a word. The words found should be output in lexicographical order (i.e. dictionary order). If no word can be formed, output nothing.

The movement between cells is illustrated by the 8 possible directions:

$$\{(-1,0), (1,0), (0,-1), (0,1), (-1,-1), (-1,1), (1,-1), (1,1)\}$$

Design an efficient solution that leverages trie data structures and depth-first search (DFS) to locate the words.

inputFormat

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

• The first line contains two integers m and n representing the number of rows and columns of the board.
• The next m lines each contain a string of n lowercase letters (with no spaces) representing a row of the board.
• The following line contains an integer k indicating the number of words in the dictionary.
• The next k lines each contain a word.

outputFormat

Output the found words in lexicographical order to stdout, each on a separate line. If no words are found, output nothing.

## sample

4 4
oaan
etae
ihkr
iflv
4
oath
pea
eat
rain

eat
oath

</p>