G. I love Codeforces
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Среди участников соревнований по программированию на сайте codeforces.com распространена традиция: когда участник влюбляется в другого участника, он меняет свой ник (имя, которое видят другие участники) на «I_love_<ник участника, в которого он влюбился>». К сожалению, администрация сайта по техническим причинам утеряла текущие ники участников, которые меняли ники в последнее время, но осталась информация о том, кто из них в кого влюблялся. Теперь администрации нужно написать программу, которая помогала бы определять текущий ник заданного участника. Нужно отметить, что из-за небольшой ошибки в структуре базы данных разные участники на этом сайте могут иметь одинаковые ники.

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

В первой строке содержится единственное целое число n (2 ≤ n ≤ 200000) — количество участников.

Далее в n строках записаны изначальные ники участников. Каждый из них представляет собой непустую строку длиной не более 24 символов, состоящую только из больших и малых символов латинского алфавита, а также из знаков подчёркивания. Некоторые ники могут совпадать.

В следующей строке содержится единственное целое число m (1 ≤ m ≤ 200000) — количество сообщений о том, что один из участников влюбился в другого участника.

Далее в m строках записаны пары целых чисел aj и bj через пробел (1 ≤ aj, bj ≤ n, aj ≠ bj) — сообщение о том, что aj-й участник влюбился в bj-го участника и поменял ник в соответствии с этим. Участники нумеруются с единицы в том порядке, в котором указаны их изначальные ники. Переименования происходят в том порядке, в котором они указаны.

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

В единственной строке выведите конечный ник первого участника после всех переименований.

Примеры
Входные данные
5
anonymous
natalia
LeBron
Tanya_Romanova
MikeMirzayanov
6
1 2
3 4
2 1
4 3
1 4
3 2
Выходные данные
I_love_I_love_I_love_Tanya_Romanova
Входные данные
5
anonymous
natalia
LeBron
Tanya_Romanova
MikeMirzayanov
3
2 1
1 2
1 5
Выходные данные
I_love_MikeMirzayanov
Входные данные
2
MikhailRubinchik
evol_I
1
1 2
Выходные данные
I_love_evol_I