Description

一家规模虽小但却引以为豪的公司的名称由 $n$ 个小写英文字母组成。该公司决定尝试品牌重塑，这是一种积极的营销策略，包括一系列措施来改变品牌(公司及其生产的产品)或其组成部分：名称、标识和口号。他们决定从名称入手。

为此，公司连续聘请了 $m$ 名设计师。一旦公司聘请了第 $i$ 位设计师，他就会立即参与创建新的公司名称，具体做法如下：他使用最新版本的名称，将所有字母 $x_i$ 替换为 $y_i$ ，将所有字母 $y_i$ 替换为 $x_i$ 。这样就得到了新版本。其中一些字母可能在字符串中没有出现。也可能出现 $x_i$ 与 $y_i$ 重合的情况。最后一个设计者完成工作后得到的名称版本将成为公司的新名称。

经理 小田 最近刚在这家公司找到一份工作，但他已经沉浸在团队合作的精神中，非常担心品牌重塑的成功。他自然迫不及待地想知道公司的新名称是什么。

满足 小田 的好奇心，告诉他最终版本的名称。

Input

输入的第一行包含两个整数 $n$ 和 $m$ $( 1 ≤ n, m ≤ 200 000 )$ ，分别是初始名称的长度和聘用设计师的人数。 第二行由 $n$ 个小写英文字母组成，代表公司最初的名称。 接下来的 $m$ 行包含对设计者行为的描述：其中第 $i$ 行包含两个空格分隔的小写英文字母 $x_i$ 和 $y_i$ 。

Output

输出公司的新名称。

6 1
police
p m

11 6
abacabadaba
a b
b c
a d
e g
f a
b b

molice

cdcbcdcfcdc

Note

在第二个示例中，公司名称连续变化如下：