给定一个字符串 $$$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 \le t \le 10^{3}$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行有两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 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$$$ 获取的按字典顺序排列的最小字符串。
示例
输入复制
32 2cbc bb a10 10bbbbbbbbbbb ab cc bb ac ab cb cb aa bc a30 20abcaababcbbcabcbbcabcbabbbbabcb cb cc ab cb cb ab cb cb ab ab ab ac ab cc ab cc ac ab cc b
输出复制
ab aaaaabbbbb aaaaaaaaaaaaaaabbbabcbabbbbabc
注意
在第一个测试用例中,两个操作都需要应用于第一个字母:
- 第一次操作后,$$$s =$$$ "bb"
- 第二次操作后,$$$s =$$$ "ab"
在第二个测试用例中,字符串可能会更改如下:
- "bbbbbbbbbb"(更改了第 $$$5$$$ 个字母)
- "cbbbabbbbb"(更改了 $$$1$$$-st 字母)
- "cbbbabbbbb“(什么也没做)
- "cbbaabbbbb"(更改了第 $$$4$$$ 个字母)
- "阿巴阿布"(更改了 $$$1$$$-st 字母)
- "abcaabbbbb"(更改了 $$$3$$$-rd 字母)
- "abcaabbbbb“(什么也没做)
- "aacaabbbbb"(更改了 $$$2$$$-nd 字母)
- "aacaabbbbb“(什么也没做)
- "aaaaabbbbb"(更改了 $$$3$$$-rd 字母)