← 返回题目列表

Codeforces · 1688/C

C. 操纵历史

中文机器翻译题面 查看原题

凯恩拥有操纵历史的能力。

幻想乡的历史最初是一个长度为$$$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"$$$]$$$。