Zigzag

Zig and Zag are playing a word game. Zig says one letter, and Zag says a word that starts
with that letter. However, the word needs to be from the allowed word list and such that Zag
already said it the least amount of times. If the word choice is ambiguous, then Zag will
choose the one that is lexicographically smaller (sooner in the alphabet). For each Zig’s
letter, it will be possible to choose a word.
Let there be a list consisting of exactly \(K\) distinct words and an array of \(N\) letters that Zig has
given. Write a program that will, based on the input, output an array of \(N\) words that Zag said
during the game.

In test cases worth 60% of total points, it will hold that \(N\) and \(K\) are smaller than 500.

The first line of input contains positive integers \(K\) (\(1 \le K \le 100\,000\)) and \(N\) (\(1 \le N \le 100\,000\))
from the task.
Each of the following \(K\) lines contains a single word consisting of lowercase letters of the
English alphabet not longer than 21 characters.
Each of the following \(N\) lines contains a single lowercase letter of the English alphabet.

You must output \(N\) lines, each containing a single word from the task.

생성자가 기록되지 않았습니다.

출처 COCI 2017/2018 Contest 2