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.

Input Specification

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.

Output Specification

You must output ~N~ lines, each containing a single word from the task.

Scoring

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