ZigZag

Zig and Zag play a word game. Zig says one lowercase letter, and Zag answers with a word that starts with that letter. The word must come from a fixed word list, and among the words on the list that start with that letter, Zag says the one he has said the fewest times so far. If several words tie, Zag says the one that comes first in alphabetical order. For every letter Zig says, a word is always available.

You are given a list of $K$ distinct words and the $N$ letters Zig says. Write a program that prints the $N$ words Zag says, in order.

The first line contains $K$ ($1 \le K \le 100\,000$) and $N$ ($1 \le N \le 100\,000$).

Each of the next $K$ lines contains one word, a string of lowercase English letters of length at most $21$.

Each of the next $N$ lines contains one lowercase English letter that Zig says.

Print $N$ lines. Line $i$ contains the word Zag says in answer to the $i$-th letter.