309492: CF1688C. Manipulating History
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
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$。输入的字符串仅由小写英语字母组成。保证初始的字符串存在且唯一。 **输出格式** 对于每组数据，输出幻想乡最一开始的历史。题目描述
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.输入输出格式
输入格式
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 < 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.
输出格式
For each test case, print the initial string in one line.
输入输出样例
输入样例 #1
2
2
a
ab
b
cd
acd
3
z
a
a
aa
yakumo
ran
yakumoran输出样例 #1
a
z说明
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.Input
题意翻译
> 身为人类时，她的能力是将已有的历史全盘抹消；变身为白泽时，则能创造历史。——《东方求闻史纪》 上白泽慧音具有操作历史程度的能力。 幻想乡的历史，一开始是一个长度为 $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$。输入的字符串仅由小写英语字母组成。保证初始的字符串存在且唯一。 **输出格式** 对于每组数据，输出幻想乡最一开始的历史。Output
**题意翻译**
身为人类时，她的能力是将已有的历史全盘抹消；变身为白泽时，则能创造历史。——《东方求闻史纪》
上白泽慧音具有操作历史程度的能力。
幻想乡的历史，一开始是一个长度为 $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$。输入的字符串仅由小写英语字母组成。保证初始的字符串存在且唯一。
**输出格式**
对于每组数据，输出幻想乡最一开始的历史。
**题目描述**
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.
**输入输出格式**
**输入格式**
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 < 10 ^ 5 $ ) — the number of operations.
The next $ 2n $ lines contains one non-empty string $ t_{i} $ — the**题意翻译** 身为人类时，她的能力是将已有的历史全盘抹消；变身为白泽时，则能创造历史。——《东方求闻史纪》 上白泽慧音具有操作历史程度的能力。 幻想乡的历史，一开始是一个长度为 $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$。输入的字符串仅由小写英语字母组成。保证初始的字符串存在且唯一。 **输出格式** 对于每组数据，输出幻想乡最一开始的历史。 **题目描述** 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. **输入输出格式** **输入格式** 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 < 10 ^ 5 $ ) — the number of operations. The next $ 2n $ lines contains one non-empty string $ t_{i} $ — the
身为人类时，她的能力是将已有的历史全盘抹消；变身为白泽时，则能创造历史。——《东方求闻史纪》
上白泽慧音具有操作历史程度的能力。
幻想乡的历史，一开始是一个长度为 $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$。输入的字符串仅由小写英语字母组成。保证初始的字符串存在且唯一。
**输出格式**
对于每组数据，输出幻想乡最一开始的历史。
**题目描述**
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.
**输入输出格式**
**输入格式**
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 < 10 ^ 5 $ ) — the number of operations.
The next $ 2n $ lines contains one non-empty string $ t_{i} $ — the**题意翻译** 身为人类时，她的能力是将已有的历史全盘抹消；变身为白泽时，则能创造历史。——《东方求闻史纪》 上白泽慧音具有操作历史程度的能力。 幻想乡的历史，一开始是一个长度为 $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$。输入的字符串仅由小写英语字母组成。保证初始的字符串存在且唯一。 **输出格式** 对于每组数据，输出幻想乡最一开始的历史。 **题目描述** 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. **输入输出格式** **输入格式** 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 < 10 ^ 5 $ ) — the number of operations. The next $ 2n $ lines contains one non-empty string $ t_{i} $ — the