407071: GYM102697 042 Number Code (Harder Version)

Note: this is a harder version of a previous problem in the contest.

You are using a code where letters in words map to digits in the following way:

0 = o

1 = i

3 = e

4 = a

5 = s

7 = t

(the other digits will not be used in this problem)

You've found a sequence of numbers, and you want to find how many words the numbers correspond to using the code described above.

Additionally, for this problem, assume that any letters in the original word that did not map to a letter in the code were simply encoded as blanks. Thus, a number sequence can potentially map to multiple words. Thus, you are given a dictionary of words, and you are tasked with figuring out which words in the dictionary map to the given number sequence.

The first line of input contains a positive integer D: the number of words in the dictionary. The next D lines each contain a single word: each dictionary entry. The words will be sorted alphabetically. The next line of input contains a positive integer T indicating the number of test cases that follow. The next T lines each contain a single number sequence (not separated by spaces).

For each test case, first print a positive integer K: the number of single words in the dictionary that map to the number sequence using the code described above. Then, print K lines: each word, printing the words in alphabetical order (remember that the given dictionary already is in alphabetical order).

8
fantastic
funtastuc
hasty
taste
tasted
tastes
tasty
untasty
3
457
7457
74573

1
hasty
3
funtastuc
tasty
untasty
2
taste
tasted