Hide

Problem NWordle with Friends

Zoe and her friends enjoy playing Wordle1 together and have decided to work cooperatively to solve the daily puzzle.

Wordle is a game where players get six attempts to guess a hidden 5-letter word. With each word guessed, the system will mark each letter with one of three feedback colors:

1. Green - this letter is in the word and occurs at this location.

2. Yellow - this letter is in the word, but not at this location.

3. Gray - this letter is not in the hidden word (with an exception for duplicate letters, see below).

Note that duplicate letters can be a little tricky. First, Green letters are marked. For a single letter, suppose there are $X$ non-Green occurrences in the hidden word and $Y$ non-Green occurrences in the guess. The leftmost $\min (X,Y)$ of the non-Green occurrences of this letter will be marked Yellow and the rest will be Gray.

For example, if the hidden word was FREED and a guessed word was GEESE, the feedback would show the second E (the third letter) in Green, and the first and third Es (second and fifth letters of GEESE) respectively in Yellow and Gray.

Knowing the list of all guessable words, help Zoe determine which words are still valid given their original guesses.

Input

The first line of input contains two integers $N$ ($1 \leq N \leq 10$), which is the number of guesses Zoe and her friends have made, and $W$ ($1 \leq W \leq 10^4$), which is the number of guessable words.

The next $N$ lines describe the guesses. Each line contains two 5-letter strings $g$ and $f$. The first string, $g$, is the guess which consists only of uppercase English letters and is in the list of guessable words. The second string, $f$, is the feedback. The feedback is composed of the characters G, Y, and -, respectively indicating Green, Yellow, and Gray for the guess.

The last $W$ lines describe the list of distinct guessable words. Each line contains a 5-letter string of uppercase English letters.

Output

Display all valid words, in the order they appear, from the guessable list of words. There will always be at least one valid word.

Sample Input 1 Sample Output 1
2 5
BERRY -G---
APPLE ---YY
MELON
BERRY
LEMON
LIMES
APPLE

MELON
LEMON

Sample Input 2 Sample Output 2
3 5
BERRY -G---
APPLE ---YY
LIMES G-GY-
APPLE
BERRY
LEMON
LIMES
MELON

LEMON

Sample Input 3 Sample Output 3
3 5
BLANK --Y--
SIGHS ----G
STORM YGG-Y
ATOMS
BLANK
MOATS
SIGHS
STORM

ATOMS

Sample Input 4 Sample Output 4
4 5
FRUIT -G--Y
NUTTY --Y--
ROOTS Y--YG
SEEDS -YG-G
FRUIT
NUTTY
ROOTS
SEEDS
TREES

TREES


Footnotes

1. Wordle was created by Josh Wardle, and is now owned by the New York Times.
Hide