Deren and Aslı are best friends. They get on really well. However, Aslı has a problem. Deren eats a lot and when he is eating, Aslı can not understand what he is saying. When he speaks while eating, Deren tends to replace certain characters with other characters, so Aslı prepared a list of replacement rules in her notebook. Help her find the actual sentence Deren intends to say.

Input

The first line contains Deren's speech as a string \(s\) consisting of lowercase ASCII characters and spaces. The second line contains a positive integer \(n\), the number of replacements in Aslı's notebook. The next \(n\) lines contain two characters \(a_i\) and \(b_i\), which denotes that Deren pronounces the character \(a_i\) as \(b_i\) while eating.

Output

A single line containing Deren's original sentence

Constraints

• 1 <= \(len(s)\) <= \(10^5\)
• 1 <= \(n\) <= 1000

Aslı cannot hold 1000 rules in her memory, so her notebook can contain:

• Multiple copies of a rule, such as "(a b), (a b), ..., (a b)".
• Cyclic rules, such as "(b a), (c b), (a c)"
• Contradicting rules, such as "(b a), (c a)".

In a such case, assume the last rule has priority. In other words, you will apply the rules in reverse order they appear in the input.

• Deren's sentence is guaranteed to be recoverable by applying the replacements.

Examples

Input

mewhaba
1
r w

Output

merhaba

Input

aaaa aaa
3
a b
b c
c a

Output

aaaa aaa

Input

beren
2
d b
q b

Output

qeren