Word Search Puzzle

You are given a list of words and a grid of uppercase letters. Your task is to find all the words from the given list that can be formed in the grid by tracing a path from letter to letter. The path can move in any of the 8 directions (horizontally, vertically, or diagonally). A cell may be used only once in the formation of a single word.

Note: The search is case-sensitive and all letters are uppercase. The output should list the found words in lexicographical order separated by a single space. If no word can be found, output an empty line.

Hint: Use Depth First Search (DFS) with backtracking to explore the grid.

For example, if the word list is [CAT, DOG, COW] and the grid is:

CAT
DOG
CAT

Then the words that can be formed are CAT and DOG, and the output (after sorting lexicographically) will be:

CAT DOG

inputFormat

The input is given from stdin in the following format:

1. An integer N that represents the number of words.
2. A line with N uppercase words separated by spaces.
3. Two integers R and C representing the number of rows and columns of the grid.
4. R lines follow, each containing a string of exactly C uppercase letters.

outputFormat

Print a single line to stdout containing all the words found in the grid sorted in lexicographical order and separated by a single space. If no valid word is found, print an empty line.

## sample

3
CAT DOG COW
3 3
CAT
DOG
CAT

CAT DOG