Transform and Sort Words

You are given T test cases. In each test case, you are provided with a list of M words and N transformation rules. Each transformation rule is given in the format X Y, meaning that every occurrence of character \(X\) in a word should be replaced by character \(Y\). After applying all the specified transformations on each word, you must sort the resulting words in lexicographical (alphabetical) order and output them.

Input Format: The input begins with an integer \(T\), the number of test cases. For each test case:

• An integer \(M\) denoting the number of words.
• A single line containing \(M\) words separated by spaces.
• An integer \(N\) denoting the number of transformation rules.
• \(N\) lines follow, each containing two characters separated by a space representing a transformation rule.

Output Format: For each test case, output a single line with the sorted list of transformed words, separated by a single space.

Example:

Input:
1
3
cat bat rat
2
a o
 t r
Output:
bor cor ror

</p>

Note: If there is no transformation rule provided (i.e. \(N = 0\)), output the original words sorted lexicographically. If the word list is empty, output an empty line.

inputFormat

The first line contains an integer \(T\) \( (1 \leq T \leq 10)\), the number of test cases. For each test case, the following input is provided:

• An integer \(M\) denoting the number of words.
• A line containing \(M\) space separated words.
• An integer \(N\) denoting the number of transformation rules.
• \(N\) lines each containing two characters separated by a space.

It is guaranteed that each word consists only of lowercase English letters and each transformation rule is in the format X Y where \(X\) and \(Y\) are lowercase English letters.

outputFormat

For each test case, output a single line containing the transformed and lexicographically sorted list of words. The words should be space separated.

## sample

1
3
cat bat rat
2
a o
t r

bor cor ror