AquaMoon 有 $$$n$$$ 个长度为 $$$m$$$ 的字符串。 $$$n$$$ 是奇数。
当AquaMoon消失后,琪露诺试图将这些$$$n$$$字符串配对在一起。在制作 $$$\frac{n-1}{2}$$$ 对后,她发现恰好有一个字符串没有该对!
在她的愤怒中,她打乱了每一对琴弦。对于每一对,她选择了一些位置(至少 $$$1$$$ 和最多 $$$m$$$),并在所选位置交换了该对的两个字符串中的字母。
例如,如果 $$$m = 6$$$ 并且两个字符串“abcdef”和“xyzklm”是一对,并且 Cirno 选择了位置 $$$2$$$、$$$3$$$ 和 $$$6$$$,她会将“b”替换为“y”,将“c”替换为“z”,将“f”替换为“m”。生成的字符串将为“ayzdem”和“xbcklf”。
琪露诺随后偷走了没有配对的字符串,并将所有剩余的字符串以任意顺序洗牌。
AquaMoon 发现剩余的 $$$n-1$$$ 字符串完全混乱。此外,她还记得最初的 $$$n$$$ 字符串。她想知道哪根绳子被偷了,但她不擅长编程。你能帮助她吗?
输入
这个问题是交互式的。这意味着您的解决方案将读取交互器给出的输入。但是交互器会在开始时为您提供完整的输入,之后您应该打印答案。因此,您应该解决问题,就像解决通常的非交互式问题一样,因为您不会有任何交互过程。您不应该忘记的唯一一件事是在打印答案后刷新输出缓冲区。否则,您可能会得到“超出空闲限制”的判决。有关刷新输出缓冲区的详细信息,请参阅交互式问题指南。
输入由多个测试用例组成。第一行包含一个整数 $$$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$$$的字符串,描述了琪露诺交换并重新排序后的字符串。
保证 $$$n$$$ 为奇数,并且所有测试用例的 $$$n \cdot m$$$ 之和不超过 $$$10^5$$$。
黑客格式:
第一行应包含单个整数 $$$t$$$。之后 $$$t$$$ 测试用例应遵循以下格式:
第一行应包含两个整数 $$$n$$$ 和 $$$m$$$。
以下 $$$n$$$ 行应包含 $$$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$$$ 的整数排列,描述字符串应重新排序的方式。字符串将按照此排列中放置的顺序索引放置,被盗的字符串索引将被忽略。
输出
对于每个测试用例,用被盗的字符串打印一行。
示例
输入 #1
3 3 5 aaaaa bbbbb ccccc aaaaa bbbbb 3 4 aaaa bbbb cccc aabb bbaa 5 6 abcdef uuuuuu kekeke ekekek xyzklm xbcklf eueueu ayzdem ukukuk
输出 #1
ccccc cccc kekeke
注意
在第一个测试用例中,“aaaaa”和“bbbbb”交换了所有位置,“ccccc”是被盗的字符串。
在第二个测试用例中,“aaaa”和“bbbb”交换了两个第一个位置,“cccc”是被盗的字符串。
这是 hack 格式的第一个测试: