Searching up words in a dictionary can be painstaking. That's why we've come up with an online dictionary that makes it really easy to search for words. To make life easier for the user, you can insert the following characters to broaden your search:
- ? - matches any single character
- * - matches any series of 0 or more characters
For example, the search D??? matches all four letter words with prefix 'D' (e.g. DIRT, DUST, DUNK, etc...). Given a dictionary of words and a few search queries, give the list of words returned by each query.
The input file DATA5.txt will contain 5 test cases. The first line of each test case contains an integer 1 <= N <= 1000, the number of words in the dictionary. The next N lines each contain a unique word, consisting of only capital letters, up to 256 characters in length. The next 5 lines are test queries, consisting of capital letters, ? and *.
The output file OUT5.txt will contain 5 lines per test case, 25 in total. Each line is a comma separated (with a space) list of all matches found in the dictionary. The results in the list appear in the same order as they do in the supplied dictionary. If no match is found output NO MATCH
Refer to the sample output for formatting.
6 BELLS TELLS FALLS DOLLS DULLS DOLLIES SELLS *ELLS D?LLS D?LL* *LL*
NO MATCH BELLS, TELLS DOLLS, DULLS DOLLS, DULLS, DOLLIES BELLS, TELLS, FALLS, DOLLS, DULLS, DOLLIES