Word Games

The cows are playing a word-tile game, but sadly they lack the vocabulary to play at the tournament level. Bessie just wants your help with the very first move.

You are given a rack (a rack is a holder for the letter tiles) of $N$ letters ($3 \le N \le 10$), which may repeat and may include one or more blank "wildcard" tiles, together with a dictionary of $D$ words ($10 \le D \le 50000$). By searching the dictionary, print every word Bessie could play.

The 27 possible rack symbols are the upper-case letters 'A'..'Z' and the '#' symbol, which is a wildcard that can stand for any single letter. If two '#'s appear in one rack, each can represent a different letter.

A word can be played when every letter of the word can be matched to a tile in the rack; that is, the word's multiset of letters must be a sub-multiset of the rack's, and each '#' can cover one missing letter. Bessie's rack can always form at least one word. Every dictionary word is unique and upper-case.

• Line 1: two space-separated integers $N$ and $D$.
• Line 2: the $N$ letters of Bessie's rack, with no intervening spaces.
• Next $D$ lines: one dictionary word per line.

• Print every word Bessie can play, one per line, in the order the words appear in the dictionary (the input order).