题目描述

给定一个仅由拉丁字母表前三个字母组成的字符串 $s$，即字符串中的每个字符要么是 $a$、$b$，要么是 $c$。

同时给定需要在字符串上执行的 $q$ 个操作。每个操作提供两个字母 $x$ 和 $y$（来自拉丁字母表的前三个字母），对于每个操作，必须执行以下两种操作之一：

• 将字符串 $s$ 中任意一个字母 $x$ 的出现更改为字母 $y$（如果至少存在一个字母 $x$ 的出现）；
• 不执行任何操作。

目标是以给定的顺序执行所有操作，使得字符串 $s$ 在字典序上最小。

回忆一下，字符串 $a$ 在字典序上小于字符串 $b$ 当且仅当以下条件之一成立：

• $a$ 是 $b$ 的前缀，但 $a \neq b$；
• 在 $a$ 和 $b$ 第一个不同的位置上，$a$ 中的字母在字母表中比 $b$ 中对应的字母更靠前。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^3$）——测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 2 \cdot 10^5$）——字符串 $s$ 的长度和操作的数量。

每个测试用例的第二行给出字符串 $s$ —— 一个恰好由 $n$ 个字符组成的字符串，每个字符是 $a$、$b$ 或 $c$。

每个测试用例接下来的 $q$ 行包含操作的描述。每行包含两个字符 $x$ 和 $y$，每个字符是 $a$、$b$ 或 $c$。

输入的其他约束：

• 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$；
• 所有测试用例的 $q$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出通过给定操作可以从 $s$ 获得的字典序最小的字符串。

3
2 2
cb
c b
b a
10 10
bbbbbbbbbb
b a
b c
c b
b a
c a
b c
b c
b a
a b
c a
30 20
abcaababcbbcabcbbcabcbabbbbabc
b c
b c
c a
b c
b c
b a
b c
b c
b a
b a
b a
b a
c a
b c
c a
b c
c a
c a
b c
c b

ab
aaaaabbbbb
aaaaaaaaaaaaaaabbbabcbabbbbabc

样例解释

在第一个测试用例中，需要对第一个字母应用两个操作：

1. 第一次操作后，( s = "bb" )；
2. 第二次操作后，( s = "ab" )。

在第二个测试用例中，字符串的变化过程如下：

1. "bbbbabbbbbb"（修改第5个字母）；
2. "cbbbabbbbbb"（修改第1个字母）；
3. "cbbbabbbbbb"（未执行任何操作）；
4. "cbbaabbbbbb"（修改第4个字母）；
5. "abbaabbbbbb"（修改第1个字母）；
6. "abcaabbbbbb"（修改第3个字母）；
7. "abcaabbbbbb"（未执行任何操作）；
8. "aacaabbbbbb"（修改第2个字母）；
9. "aacaabbbbbb"（未执行任何操作）；
10. "aaaaabbbbbb"（修改第3个字母）。