Description

在传输信息的过程中，为了保证信息的安全，我们需要对原信息进行加密处理，形成加密信息，从而使得信息内容不会被监听者窃取。现在给定一个长度为 $n$ 的字符串，对其进行加密处理。

加密的规则如下：给出 $m$ 个字符对，如给出字符对 $(x, y)$ 则在字符串中将字符 $x$ 加密为 $y$。请注意，给出一个加密信息后请立即加密。请你输出加密后的字符串。所给字符串及字符对只包含小写英文字母。

Format

Input

第一行输入两个整数 $n, m(1 \leq n, m \leq 100)$第二行输入一个长度为 $n$ 的字符串 $s$接下来 $m$ 行，每行输入两个字符

Output

输出加密后的字符串

Samples

8 1
wxmhhorz
h g

wxmggorz

8 3
wxoggtuy
o m
u q
y l

wxmggtql

3 3
abc
a b
b c
c a

aaa

Hint