题目内容

魔术师面前有一排宝石，共有 $n$ 颗，每颗宝石的颜色均为一个小写字母。他将依次施展 $q$ 次法术，每次法术会给出两个字母 $x$ 和 $y$，效果是将当前所有颜色为 $x$ 的宝石变成颜色 $y$。请你帮助魔术师计算在所有法术结束后，这排宝石最终的颜色序列。

宝石数量 $n$ 和法术次数 $q$ 均不超过 4×10^5，且所有测试数据中 $n$ 的总和与 $q$ 的总和分别不超过 4×10^5。测试数据组数 $T$ 不超过 10。所有颜色均为小写字母。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。

每组测试数据描述如下：

• 第一行包含两个整数 $n$ 和 $q$，分别表示宝石数量和法术次数；
• 第二行包含一个长度为 $n$ 的字符串，表示初始颜色序列；
• 接下来 $q$ 行，每行包含两个小写字母 $x$ 和 $y$，表示一次法术。

输出描述

对于每组测试数据，输出一行一个字符串，表示最终的颜色序列。

样例1

输入

1
4 2
aabb
a b
b c

输出

cccc

说明

初始宝石序列为 aabb，共有 4 颗宝石。

第一次法术 $a \\to b$ 将所有 a 变为 b，序列变为 bbbb。第二次法术 $b \\to c$ 将所有 b 变为 c，序列变为 cccc。在映射维护中，最终原字符 a 和 b 都会映射到 c，因此输出全部为 c。

样例2

输入

2
5 3
hello
h y
e a
l o
3 0
abc

输出

yaooo
abc

说明

第一组数据：初始序列 hello，共 5 颗宝石，3 次法术。法术 $h \\to y$ 将 h 变为 y；$e \\to a$ 将 e 变为 a；$l \\to o$ 将 l 变为 o。没有涉及 o 的法术，o 保持不变。最终序列为 yaooo。

第二组数据：初始序列 abc，共 3 颗宝石，法术次数 $q=0$，没有任何变化，最终序列仍为 abc。该样例展示了无操作时的边界情况。

样例3

输入

1
6 4
abcdef
a b
b c
c d
a e

输出

ddddef

说明

初始序列 abcdef，共 6 颗宝石，4 次法术。

• 法术 $a \\to b$：当前映射为 a 的改为 b，原 a 映射到 b。
• 法术 $b \\to c$：当前映射为 b 的（即原 a 和原 b）都改为 c。
• 法术 $c \\to d$：当前映射为 c 的（原 a、b、c）都改为 d。
• 法术 $a \\to e$：扫描所有字母，发现已经没有任何字符映射到 a，因此该次法术不影响任何映射。

最终，原 a、b、c 均映射为 d，原 d 映射为 d，原 e 映射为 e，原 f 映射为 f。序列变为 ddddef。

这个样例展示了当映射已经被之前的操作改变后，对已变化字符的法术不再产生效果。