CF1546B AquaMoon and Stolen String

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$ 个字符串。她想知道被偷走的是哪一个字符串，但她不擅长编程。你能帮帮她吗？

本题为交互题。这意味着你的程序需要读取交互器给出的输入。但交互器会在一开始就给出全部输入，之后你只需输出答案。因此你可以像做普通非交互题一样解题，因为没有交互过程。唯一要注意的是，输出答案后需要刷新输出缓冲区，否则可能会收到 "Idleness limit exceeded" 的判罚。详细信息请参考 [交互题指南](https://codeforces.com/blog/entry/45307)。 输入包含多组测试数据。第一行包含一个整数 $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$ 的字符串，表示原始字符串。 接下来 $\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$ 的一个排列，表示字符串被重新排列的顺序，被偷走的字符串下标会被忽略。

对于每组测试数据，输出一行，被偷走的字符串。

在第一个测试点中，"aaaaa" 和 "bbbbb" 交换了所有位置，"ccccc" 被偷走。 在第二个测试点中，"aaaa" 和 "bbbb" 交换了前两个位置，"cccc" 被偷走。 以下是 hack 格式的第一个测试点： ```

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


```

由 ChatGPT 4.1 翻译