P4432 [COCI 2017/2018 #2] ​​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.

The first line of input contains positive integers K (1 ≤ K ≤ 100 000) and N (1 ≤ N ≤ 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.

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