Making Words

A 3 by 3 puzzle board contains one uppercase English letter in each cell. Using the letters on the board, you can form words from a dictionary. A word must have at least 4 letters, and each cell may be used at most once, so a repeated letter can be used only as many times as it appears on the board. The letter placed in the center cell must also be included in the word.

The 9 letters to place on the board are already fixed, but the center letter has not been chosen yet. Depending on which letter is placed in the center, the number of dictionary words that can be made changes.

Given a dictionary and several puzzle boards, determine for each board which center letters minimize the number of possible words and which center letters maximize it, together with those word counts.

The input first gives the dictionary, one word per line. The dictionary contains at most 200,000 words. Each word consists only of 4 to 9 uppercase English letters. The words are sorted in lexicographic order. A line containing a single - marks the end of the dictionary.

After that, several puzzle boards are given. Each board is a line containing exactly 9 uppercase English letters. A line containing a single # marks the end of the input.

For each puzzle board, print one line containing the following four values separated by spaces.

1. The distinct center letters, in alphabetical order, that make the number of possible words as small as possible
2. That minimum number of words
3. The distinct center letters, in alphabetical order, that make the number of possible words as large as possible
4. That maximum number of words

If multiple letters achieve the same minimum or maximum, print all of them once in alphabetical order. Even if a letter appears multiple times on the board, it appears at most once in the output.