B. Лекция
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас новый преподаватель по теории графов и он очень быстро читает лекции. Чтобы успевать записывать, вы разработали следующий план.

Вы знаете два языка, причём преподаватель читает лекцию на первом из них. Слова обоих языков состоят из маленьких латинских символов. Каждый язык представляет собой некоторый набор слов. В каждом языке все слова различаются, т. е. записываются различным образом. Более того, между словами этих языков установлено взаимно-однозначное соответствие, то есть для каждого слова каждого языка в другом языке существует ровно одно слово, которое имеет такое же значение.

Каждое слово, сказанное преподавателем, вы можете написать либо на первом языке, либо на втором. Конечно, во время лекции каждое слово вы записываете на том языке, на котором данное слово записывается короче. В случае равенстве длин соответствующих слов вы отдаете предпочтение слову из первого языка.

Вам задан текст лекции, которую прочитает вам преподаватель. Определите, как описанная лекция будет записана вами в конспект.

Входные данные

В первой строке записано два целых числа n и m (1 ≤ n ≤ 3000, 1 ≤ m ≤ 3000)— количество слов в лекции преподавателя и количество слов в каждом из языков. В следующих m строках записано описание слов. i-я строка содержит две строки ai, bi. Это означает, что слово ai принадлежит первому языку, слово bi принадлежит второму языку, и эти два слова обозначают одно и то же. Гарантируется, что никакое слово не встречается в обоих языках и каждое слово встречается ровно один раз в своем языке.

В следующей строке записано n строк через пробел c1, c2, ..., cn — описание лекции. Гарантируется, что каждая из строк ci принадлежит множеству строк {a1, a2, ... am}.

Все строки во входных данных непусты, каждая из них состоит из не более чем 10 маленьких латинских букв.

Выходные данные

Выведите ровно n строк — описание того, как вы запишите лекцию в свою тетрадь. Слова лекции требуется выводить в том же порядке, что и во входных данных.

Примеры
Входные данные
4 3
codeforces codesecrof
contest round
letter message
codeforces contest letter contest
Выходные данные
codeforces round letter round
Входные данные
5 3
joll wuqrd
euzf un
hbnyiyc rsoqqveh
hbnyiyc joll joll euzf joll
Выходные данные
hbnyiyc joll joll un joll