Wordle with Friends

문제

Zoe and her friends enjoy playing Wordle (Wordle was created by Josh Wardle, and is now owned by the New York Times.) 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 $XX$ non-Green occurrences in the hidden word and $YY$ non-Green occurrences in the guess. The leftmost $\min (X,Y)\backslash 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.

입력

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

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

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

출력

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

2 5
BERRY -G---
APPLE ---YY
MELON
BERRY
LEMON
LIMES
APPLE

MELON
LEMON

3 5
BERRY -G---
APPLE ---YY
LIMES G-GY-
APPLE
BERRY
LEMON
LIMES
MELON

LEMON

3 5
BLANK --Y--
SIGHS ----G
STORM YGG-Y
ATOMS
BLANK
MOATS
SIGHS
STORM

ATOMS

4 5
FRUIT -G--Y
NUTTY --Y--
ROOTS Y--YG
SEEDS -YG-G
FRUIT
NUTTY
ROOTS
SEEDS
TREES

TREES