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 \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.
In test cases worth 60% of total points, it will hold that ~N~ and ~K~ are smaller than 500.
Sample Input 1
4 5 zagreb split zadar sisak z s s z z
Sample Output 1
zadar sisak split zagreb zadar
Sample Input 2
5 3 london rim pariz moskva sarajevo p r p
Sample Output 2
pariz rim pariz
Sample Input 3
1 3 zagreb z z z
Sample Output 3
zagreb zagreb zagreb