G. I love Codeforces
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Among participants of programming contests at codeforces.com the following tradition is common: whenever a participant falls in love with another participant, he changes his nickname to «I_love_<nickname of the participant he fell in love with>». Unfortunately, for technical reasons site administration has lost the current nicknames of participants who had changed their nicknames recently, but the information about who of them fell in love with whom remains. Now the administration needs to write a program for determining the current nickname of the given participant. It should be noted that due to the small bug in the database structure different participants can have the same nicknames on this site.

Input

The first line contains a single integer n (2 ≤ n ≤ 200000) — the number of participants.

In the next n lines initial nicknames of participants are given. Each nickname is a non-empty string of length at most 24 characters, consisting only of uppercase and lowercase Latin letters and also underscores. Some nicknames can coincide.

The next line contains a single integer m (1 ≤ m ≤ 200000) — the number of records that one of the participants fell in love with another participant.

In the next m lines pairs of integers aj and bj, separated by a space, are given (1 ≤ aj, bj ≤ n, aj ≠ bj) — a record that the aj-th participant fell in love with the bj-th participant and changed his nickname correspondingly. Participants are numbered from one in the order their initial nicknames are given. Renamings occur in the order they are given.

Output

In the only line output the final nickname of the first participant after all renamings.

Examples
Input
5
anonymous
natalia
LeBron
Tanya_Romanova
MikeMirzayanov
6
1 2
3 4
2 1
4 3
1 4
3 2
Output
I_love_I_love_I_love_Tanya_Romanova
Input
5
anonymous
natalia
LeBron
Tanya_Romanova
MikeMirzayanov
3
2 1
1 2
1 5
Output
I_love_MikeMirzayanov
Input
2
MikhailRubinchik
evol_I
1
1 2
Output
I_love_evol_I