凯恩拥有操纵历史的能力。
幻想乡的历史最初是一个长度为$$$1$$$的字符串$$$s$$$。为了解决 Yukari 造成的混乱,她需要执行以下操作 $$$n$$$ 次,第 $$$i$$$ 次:
- 她选择了 $$$s$$$ 的非空子字符串 $$$t_{2i-1}$$$。
- 她将 $$$t_{2i-1}$$$ 替换为非空字符串 $$$t_{2i}$$$。请注意,字符串 $$$t_{2i-1}$$$ 和 $$$t_{2i}$$$ 的长度可以不同。
请注意,如果 $$$t_{2i-1}$$$ 在 $$$s$$$ 中出现多次,则其中一个将被替换。
例如,让 $$$s=$$$"marisa"、$$$t_{2i-1}=$$$"a" 和 $$$t_{2i}=$$$"z"。操作后,$$$s$$$ 变为“mzrisa”或“marisz”。
经过$$$n$$$操作后,Keine得到了最终的字符串和长度为$$$2n$$$的操作序列$$$t$$$。正当凯恩认为自己已经完成的时候,由香里再次出现,并打乱了$$$t$$$的顺序。更糟糕的是,凯恩忘记了最初的历史。
帮助Keine找到幻想乡最初的历史!
回想一下,子字符串是字符串的连续字符序列。例如,对于字符串“abc”,其子字符串为:“ab”、“c”、“bc”等。但以下字符串不是它的子字符串:“ac”、“cba”、“acb”。
黑客
你无法解决这个问题。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$T$$$ ($$$1 \leq T \leq 10^3$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n < 10 ^ 5$$$) — 操作数。
接下来的 $$$2n$$$ 行包含一个非空字符串 $$$t_{i}$$$ — 打乱序列 $$$t$$$ 中的第 $$$i$$$ 字符串。
下一行包含一个非空字符串 $$$s$$$ — 最终字符串。
保证所有测试用例中给定字符串(包括$$$t_i$$$和$$$s$$$)的总长度不超过$$$2 \cdot 10 ^ 5$$$。所有给定的字符串仅由小写英文字母组成。
保证初始字符串存在。可以证明初始字符串是唯一的。
输出
对于每个测试用例,将初始字符串打印在一行中。
示例
输入 #1
2 2 a ab b cd acd 3 z a a aa yakumo ran yakumoran
输出 #1
a z
注意
测试用例1:
最初 $$$s$$$ 是“a”。
- 在第一个操作中,Keine 选择“a”,并将其替换为“ab”。 $$$s$$$ 变为“ab”。
- 在第二次操作中,Keine 选择“b”,并将其替换为“cd”。 $$$s$$$ 变为“acd”。
所以最终的字符串是“acd”,并且在打乱之前$$$t=[$$$"a", "ab", "b", "cd"$$$]$$$。
测试用例2:
最初 $$$s$$$ 是“z”。
- 在第一个操作中,Keine 选择“z”,并将其替换为“aa”。 $$$s$$$ 变为“aa”。
- 在第二次操作中,Keine 选择“a”,并将其替换为“ran”。 $$$s$$$ 变成“aran”。
- 在第三次操作中,Keine 选择“a”,并将其替换为“yakumo”。 $$$s$$$ 变成“yakumoran”。
所以最终的字符串是“yakumoran”,并且在洗牌之前$$$t=[$$$"z", "aa", "a", "ran", "a", "yakumo"$$$]$$$。