Problem Description

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 Format

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.

Output Format

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

Sample Input and Output

Input Sample #1

4 5
zagreb
split
zadar
sisak
z
s
s
z
z

Output Sample #1

zadar
sisak
split
zagreb
zadar

Input Sample #2

5 3
london
rim
pariz
moskva
sarajevo
p
r
p

Output Sample #2

pariz
rim
pariz

Input Sample #3

1 3
zagreb
z
z
z

Output Sample #3

zagreb
zagreb
zagreb

Notes

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

见题面 Input 部分

见题面 Output 部分