CF1688C Manipulating History

> 身为人类时，她的能力是将已有的历史全盘抹消；变身为白泽时，则能创造历史。——《东方求闻史纪》 上白泽慧音具有操作历史程度的能力。 幻想乡的历史，一开始是一个长度为 $1$ 的字符串 $s$。为了修复由于八云紫造成的历史错乱，她需要完成 $n$ 次操作。对于第 $i$ 次操作： - 她会选择字符串 $s$ 中的一个非空子串 $t_{2i-1}$； - 她会将 $t_{2i-1}$ 替换为 $t_{2i}$，注意这两者的长度可能是不一样的。 注意，如果 $t_{2i-1}$ 在字符串 $s$ 中出现多次，也仅仅只替换其中恰好一个。 例如，如果有一个字符串 $s=\texttt{marisa}$，$t_{2i-1}=\texttt a$，$t_{2i}=\texttt z$，那么在一次操作后，字符串 $s$ 将会变成 $\texttt{marisz}$ 或者 $\texttt{mzrisa}$。 在经过 $n$ 次这样的操作之后，慧音得到了最后的字符串以及 $2n$ 个 $t_i$。正当慧音觉得她完成了这项任务的时候，八云紫又一次出现并且打乱了所有的 $t_i$。更糟糕的是，慧音忘记了幻想乡最一开始的历史。 请你帮助慧音求出幻想乡最一开始的历史。

第一行输入一个正整数 $t(1 \leq t \leq 10^3)$，表示输入数据组数。 对于每一组数据，第一行输入一个正整数 $n(1 \leq n \leq 10^5)$，表示慧音的操作次数。 接下来 $2n$ 行，每一行输入一个非空字符串 $t_i$，表示被打乱后的字符串序列 $t$。 接下来输入一个字符串 $s$，表示最后的字符串。 数据保证 $|s|+\sum |t_i| \leq 2 \times 10^5$。输入的字符串仅由小写英语字母组成。保证初始的字符串存在且唯一。

对于每组数据，输出幻想乡最一开始的历史。

Test case 1: Initially $ s $ is "a". - In the first operation, Keine chooses "a", and replaces it with "ab". $ s $ becomes "ab". - In the second operation, Keine chooses "b", and replaces it with "cd". $ s $ becomes "acd". So the final string is "acd", and $ t=[ $ "a", "ab", "b", "cd" $ ] $ before being shuffled. Test case 2: Initially $ s $ is "z". - In the first operation, Keine chooses "z", and replaces it with "aa". $ s $ becomes "aa". - In the second operation, Keine chooses "a", and replaces it with "ran". $ s $ becomes "aran". - In the third operation, Keine chooses "a", and replaces it with "yakumo". $ s $ becomes "yakumoran". So the final string is "yakumoran", and $ t=[ $ "z", "aa", "a", "ran", "a", "yakumo" $ ] $ before being shuffled.