As should be obvious from his time at Mackenzie, Jimmy is a professional Spelling Bee-er. Of course, after his brief stint as MCPT Competitive Vice President, he forgot much of the convoluted vocabulary he once knew. However, undeterred by such a hindrance in his quest to restore himself to his former glory in the 2023 National Spelling Bee, he has turned to the next best option: cheating.
The day is now here, and Jimmy is standing at the podium, ready to hear the word he must spell. He already compiled a list of words that are likely to be asked in the spelling bee and entered their spellings into a phone that he most definitely did not sneak into the competition. He is asked to spell a word, and of course he doesn't know the exact spelling, but from his past experience as a professional spelling bee-er, he knows the length of the word and where some of the letters go. Given a list of possible words, can you figure out which words could be the word he heard?
Note: It is recommended for Python users to use Pypy
Constraints
The length of each word is at most 100.
Input Specification
The first line contains , the number of words.
The second line contains , a string consisting of lowercase latin characters or the character _
. A character that is _
means that the letter in that position could be anything, while a lowercase letter means that Jimmy is certain that the letter there is the correct letter.
The next lines contain a string , a word that could be asked at the spelling bee.
Output Specification
The first line contains , the number of potential words.
The next lines each contain a string , a word that is consistent with the information Jimmy deduced. Output the strings in the order of the input (if there are duplicates, do print them multiple times).
Sample Input
5
__pl_
apple
opppl
apples
app
haply
Sample Output
2
apple
haply
Sample Explanation
Firstly, the word must have 5 letters. This eliminates apples
and app
. Next, the third letter must be p
and the fourt l
. The only valid answers are thus apple
and haply
.
Comments