Word Search on Board with Diagonals

You are given a 2D board of characters and a list of words. A word can be constructed from letters of sequentially adjacent cells, where adjacent cells include horizontally, vertically, and diagonally neighboring cells. Each cell may be used only once for a particular word.

Your task is to output all the words that can be found on the board in lexicographical order. If a word is not found, it should not be output.

inputFormat

The input is given in the following format from stdin:

• The first line contains two integers n and m, representing the number of rows and columns of the board.
• The next n lines each contain a string of length m representing the board row (each character without spaces).
• The following line contains an integer k, the number of words to search for.
• The next k lines, each containing a word.

outputFormat

Output to stdout a single line containing all the found words in lexicographical order, separated by a single space. If no words are found, output an empty line.

4 4
oaan
etae
ihkr
iflv
4
oath
pea
eat
rain

eat oath