Word Games

Time limit1sMemory limit128 MB

Summary

Given a rack of up to 10 letters with wildcards and a dictionary of up to 50000 words, print every dictionary word whose letters can be covered by the rack, in input order.

Level: Medium4 of 10
Topics: Implementation, Brute force, String, Array
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples3

Example 1

Input

4 7
IAFR
AIR
FAIR
FAR
FIR
IF
FRIAR
GRID

Expected output

AIR
FAIR
FAR
FIR
IF

Example 2

Input

3 6
CT#
CAT
ACT
CUT
DOG
BAT
TT

Expected output

CAT
ACT
CUT
TT

Example 3
Input
```
3 5
AAB
AA
AAA
BAA
AB
ABB
```
Expected output
```
AA
BAA
AB
```