Given 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$$$.

Input

Each 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}$$$.

Output

For each test case, output the lexicographically minimal string that can be obtained from $$$s$$$ using the given operations.

Note

In 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)

Changing the String

Examples