CF1688C.Manipulating History

As a human, she can erase history of its entirety. As a Bai Ze (Hakutaku), she can create history out of nothingness.

—Perfect Memento in Strict Sense

Keine has the ability to manipulate history.

The history of Gensokyo is a string $s$ of length $1$ initially. To fix the chaos caused by Yukari, she needs to do the following operations $n$ times, for the $i$-th time:

• She chooses a non-empty substring $t_{2i-1}$ of $s$.
• She replaces $t_{2i-1}$ with a non-empty string, $t_{2i}$. Note that the lengths of strings $t_{2i-1}$ and $t_{2i}$ can be different.

Note that if $t_{2i-1}$ occurs more than once in $s$, exactly one of them will be replaced.

For example, let $s=$"marisa", $t_{2i-1}=$"a", and $t_{2i}=$"z". After the operation, $s$ becomes "mzrisa" or "marisz".

After $n$ operations, Keine got the final string and an operation sequence $t$ of length $2n$. Just as Keine thinks she has finished, Yukari appears again and shuffles the order of $t$. Worse still, Keine forgets the initial history.

Help Keine find the initial history of Gensokyo!

Recall that a substring is a sequence of consecutive characters of the string. For example, for string "abc" its substrings are: "ab", "c", "bc" and some others. But the following strings are not its substring: "ac", "cba", "acb".

Hacks

You cannot make hacks in this problem.

作为人类，她能彻底抹去历史；作为白泽（Hakutaku），她能凭空创造历史。

——《严格意义下的完美秘录》

凯宁拥有操控历史的能力。

幻想乡的历史最初是一个长度为 $1$ 的字符串 $s$。为了修复由八云紫引发的混乱，她需要执行 $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$ 次操作后，凯宁得到了最终字符串以及一个长度为 $2n$ 的操作序列 $t$。正当凯宁以为任务完成之时，八云紫再次现身，打乱了 $t$ 中各元素的顺序。更糟的是，凯宁忘记了初始的历史字符串。

请帮助凯宁找出幻想乡的初始历史！

回顾：子串是指字符串中连续的一段字符构成的序列。例如，对字符串 "abc"，其子串包括："ab"、"c"、"bc" 等；但以下字符串不是它的子串："ac"、"cba"、"acb"。

Hack

本题不允许 Hack。

Each test contains multiple test cases. The first line contains a single integer $T$ ($1 \leq T \leq 10^3$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \lt 10 ^ 5$) — the number of operations.

The next $2n$ lines contains one non-empty string $t_{i}$ — the $i$-th string of the shuffled sequence $t$.

The next line contains one non-empty string $s$ — the final string.

It is guaranteed that the total length of given strings (including $t_i$ and $s$) over all test cases does not exceed $2 \cdot 10 ^ 5$. All given strings consist of lowercase English letters only.

It is guaranteed that the initial string exists. It can be shown that the initial string is unique.

每个测试包含多个测试用例。第一行包含一个整数 $T$（$1 \leq T \leq 10^3$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \lt 10 ^ 5$），表示操作次数。

接下来的 $2n$ 行，每行包含一个非空字符串 $t_{i}$，即打乱顺序后的序列 $t$ 的第 $i$ 个字符串。

下一行包含一个非空字符串 $s$，即最终字符串。

保证所有测试用例中给定字符串（包括所有 $t_i$ 和 $s$）的总长度不超过 $2 \cdot 10 ^ 5$。所有给定字符串仅由小写英文字母组成。

保证初始字符串存在，且可以证明该初始字符串是唯一的。

For each test case, print the initial string in one line.

对于每个测试用例，在一行中输出初始字符串。

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.

测试用例 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"$]$。