Зіг і Заг грають у словесну гру. Зіг називає одну літеру, а Заг називає слово, яке починається з цієї літери. Однак слово має бути зі списку дозволених слів і таке, яке Заг вже сказав найменшу кількість разів. Якщо вибір слова неоднозначний, тоді Заг вибере те, яке лексикографічно менше (раніше за алфавітом). Для кожної літери Зіга буде можливо вибрати слово.

Нехай є список, що складається з рівно ~K~ різних слів та масив з ~N~ літер, які назвав Зіг. Напишіть програму, яка на основі вхідних даних виведе масив з ~N~ слів, які сказав Заг під час гри.

Input

Перший рядок вхідних даних містить додатні цілі числа ~K~ (~1 \leq K \leq 100,000~) та ~N~ (~1 \leq N \leq 100,000~) із задачі.

Кожен з наступних ~K~ рядків містить одне слово, що складається з малих літер англійського алфавіту довжиною не більше 21 символа.

Кожен з наступних ~N~ рядків містить одну малу літеру англійського алфавіту.

Output

Ви повинні вивести ~N~ рядків, кожен з яких містить одне слово із задачі.

У тестових випадках вартістю 60% від загальної кількості балів буде виконуватися умова, що ~N~ та ~K~ не більші за 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