E. Changing the Stringtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputGiven a string $$$s$$$ that consists only of the first three letters of the Latin alphabet, meaning each character of the string is either a, b, or c.Also given are $$$q$$$ operations that need to be performed on the string. In each operation, two letters $$$x$$$ and $$$y$$$ from the set of the first three letters of the Latin alphabet are provided, and for each operation, one of the following two actions must be taken: change any (one) occurrence of the letter $$$x$$$ in the string $$$s$$$ to the letter $$$y$$$ (if at least one occurrence of the letter $$$x$$$ exists); do nothing. The goal is to perform all operations in the given order in such a way that the string $$$s$$$ becomes lexicographically minimal.Recall that a string $$$a$$$ is lexicographically less than a string $$$b$$$ if and only if one of the following conditions holds: $$$a$$$ is a prefix of $$$b$$$, but $$$a \neq b$$$; at the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that comes earlier in the alphabet than the corresponding letter in $$$b$$$. InputEach test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^{3}$$$) — the number of test cases. The description of the test cases follows.In the first line of each test case, there are two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^{5}$$$) — the length of the string $$$s$$$ and the number of operations.In the second line of each test case, the string $$$s$$$ is given — a string of exactly $$$n$$$ characters, each of which is a, b, or c.The next $$$q$$$ lines of each test case contain the description of the operations. Each line contains two characters $$$x$$$ and $$$y$$$, each of which is a, b, or c.Additional constraints on the input: the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^{5}$$$; the sum of $$$q$$$ across all test cases does not exceed $$$2 \cdot 10^{5}$$$. OutputFor each test case, output the lexicographically minimal string that can be obtained from $$$s$$$ using the given operations.ExampleInput32 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 bOutputab
aaaaabbbbb
aaaaaaaaaaaaaaabbbabcbabbbbabc
NoteIn the first test case, both operations need to be applied to the first letter: after the first operation, $$$s = $$$ "bb" after the second operation, $$$s = $$$ "ab" In the second test case, the string could change as follows: "bbbbabbbbb" (changed the $$$5$$$-th letter) "cbbbabbbbb" (changed the $$$1$$$-st letter) "cbbbabbbbb" (did nothing) "cbbaabbbbb" (changed the $$$4$$$-th letter) "abbaabbbbb" (changed the $$$1$$$-st letter) "abcaabbbbb" (changed the $$$3$$$-rd letter) "abcaabbbbb" (did nothing) "aacaabbbbb" (changed the $$$2$$$-nd letter) "aacaabbbbb" (did nothing) "aaaaabbbbb" (changed the $$$3$$$-rd letter)