CF1546B.AquaMoon and Stolen String

AquaMoon had $n$ strings of length $m$ each. $n$ is an odd number.

When AquaMoon was gone, Cirno tried to pair these $n$ strings together. After making $\frac{n-1}{2}$ pairs, she found out that there was exactly one string without the pair!

In her rage, she disrupted each pair of strings. For each pair, she selected some positions (at least $1$ and at most $m$) and swapped the letters in the two strings of this pair at the selected positions.

For example, if $m = 6$ and two strings "abcdef" and "xyzklm" are in one pair and Cirno selected positions $2$, $3$ and $6$ she will swap 'b' with 'y', 'c' with 'z' and 'f' with 'm'. The resulting strings will be "ayzdem" and "xbcklf".

Cirno then stole away the string without pair and shuffled all remaining strings in arbitrary order.

AquaMoon found the remaining $n-1$ strings in complete disarray. Also, she remembers the initial $n$ strings. She wants to know which string was stolen, but she is not good at programming. Can you help her?

AquaMoon 有 $n$ 个长度均为 $m$ 的字符串，其中 $n$ 是奇数。

当 AquaMoon 离开后，Cirno 尝试将这 $n$ 个字符串两两配对。在组成 $\frac{n-1}{2}$ 对之后，她发现恰好剩下一个字符串无法配对！

盛怒之下，她打乱了每一对字符串：对每一对字符串，她选定若干个位置（至少 $1$ 个，至多 $m$ 个），并在这些选定的位置上交换该对中两个字符串的对应字符。

例如，若 $m = 6$，一对字符串为 "abcdef" 和 "xyzklm"，而 Cirno 选定了位置 $2$、$3$ 和 $6$，则她会交换 'b' 与 'y'、'c' 与 'z'、'f' 与 'm'，得到的新字符串为 "ayzdem" 和 "xbcklf"。

接着，Cirno 偷走了那个未配对的字符串，并将所有其余字符串以任意顺序打乱。

AquaMoon 发现剩下的 $n-1$ 个字符串完全混乱无序。此外，她还记得最初的 $n$ 个字符串。她想知道哪个字符串被偷走了，但她不擅长编程。你能帮她吗？

This problem is made as interactive. It means, that your solution will read the input, given by the interactor. But the interactor will give you the full input at the beginning and after that, you should print the answer. So you should solve the problem, like as you solve the usual, non-interactive problem because you won't have any interaction process. The only thing you should not forget is to flush the output buffer, after printing the answer. Otherwise, you can get an "Idleness limit exceeded" verdict. Refer to the interactive problems guide for the detailed information about flushing the output buffer.

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases.

The first line of each test case contains two integers $n$, $m$ ($1 \leq n \leq 10^5$, $1 \leq m \leq 10^5$) — the number of strings and the length of each string, respectively.

The next $n$ lines each contain a string with length $m$, describing the original $n$ strings. All string consists of lowercase Latin letters.

The next $n-1$ lines each contain a string with length $m$, describing the strings after Cirno exchanged and reordered them.

It is guaranteed that $n$ is odd and that the sum of $n \cdot m$ over all test cases does not exceed $10^5$.

Hack format:

The first line should contain a single integer $t$. After that $t$ test cases should follow in the following format:

The first line should contain two integers $n$ and $m$.

The following $n$ lines should contain $n$ strings of length $m$, describing the original strings.

The following $\frac{n-1}{2}$ lines should describe the pairs. They should contain, in the following order: the index of the first string $i$ ($1 \leq i \leq n$), the index of the second string $j$ ($1 \leq j \leq n$, $i \neq j$), the number of exchanged positions $k$ ($1 \leq k \leq m$), and the list of $k$ positions that are exchanged ($k$ distinct indices from $1$ to $m$ in any order).

The final line should contain a permutation of integers from $1$ to $n$, describing the way the strings should be reordered. The strings will be placed in the order indices placed in this permutation, the stolen string index will be ignored.

本题为交互式题目。这意味着你的程序将读取由交互器（interactor）提供的输入。但交互器会在开始时一次性给出全部输入，之后你只需输出答案即可。因此，你应像求解普通非交互式题目一样求解本题，因为实际并不存在交互过程。你唯一需要注意的是：在输出答案后，必须刷新输出缓冲区；否则，你可能会收到 “Idleness limit exceeded”（空闲时间超限）的判题结果。关于刷新输出缓冲区的详细信息，请参阅交互式题目指南。

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 10^5$，$1 \leq m \leq 10^5$），分别表示字符串的数量以及每个字符串的长度。

接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串，描述原始的 $n$ 个字符串。所有字符串均由小写拉丁字母组成。

再接下来的 $n-1$ 行，每行包含一个长度为 $m$ 的字符串，描述 Cirno 交换并重新排序后的字符串。

保证 $n$ 为奇数，且所有测试用例中 $n \cdot m$ 的总和不超过 $10^5$。

Hack 格式：

第一行应为一个整数 $t$。随后是 $t$ 个测试用例，格式如下：

第一行应包含两个整数 $n$ 和 $m$。

接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串，描述原始的 $n$ 个字符串。

再接下来的 $\frac{n-1}{2}$ 行用于描述交换操作对。每行应按以下顺序包含：第一个字符串的索引 $i$（$1 \leq i \leq n$）、第二个字符串的索引 $j$（$1 \leq j \leq n$，且 $i \neq j$）、交换的位置数量 $k$（$1 \leq k \leq m$），以及 $k$ 个待交换的位置（即 $k$ 个互不相同的、取值范围为 $1$ 到 $m$ 的下标，顺序任意）。

最后一行应为 $1$ 到 $n$ 的一个排列，表示字符串应被重排成的顺序。字符串将按照该排列中所列索引的顺序放置，而被窃取的字符串的索引将被忽略。

For each test case print a single line with the stolen string.

对于每个测试用例，输出一行被盗的字符串。

In the first test case, "aaaaa" and "bbbbb" exchanged all positions, and "ccccc" is the stolen string.

In the second test case, "aaaa" and "bbbb" exchanged two first positions, and "cccc" is the stolen string.

This is the first test in the hack format:

3
3 5
aaaaa
bbbbb
ccccc
1 2 5 1 2 3 4 5
2 1 3
3 4
aaaa
bbbb
cccc
1 2 2 1 2
2 1 3
5 6
abcdef
uuuuuu
kekeke
ekekek
xyzklm
1 5 3 2 3 6
2 4 3 2 4 6
5 4 1 2 3

在第一个测试用例中，“aaaaa”与“bbbbb”交换了所有位置，而“ccccc”是被窃取的字符串。

在第二个测试用例中，“aaaa”与“bbbb”交换了前两个位置，而“cccc”是被窃取的字符串。

这是 Hack 格式下的第一个测试：

3
3 5
aaaaa
bbbbb
ccccc
1 5 3 2 3 6
2 4 3 2 4 6
5 4 1 2 3
2 1 3
3 4
aaaa
bbbb
cccc
1 2 2 1 2
2 1 3
5 6
abcdef
uuuuuu
kekeke
ekekek
xyzklm
1 5 3 2 3 6
2 4 3 2 4 6
5 4 1 2 3