[Solution] Manipulating History Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Manipulating History Codeforces Solution | Codeforces Problem Solution 2022

C. Manipulating History

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Keine has the ability to manipulate history.

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

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

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

Solution Click Below:-  CLICK HERE

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

After n$n$ operations, Keine got the final string and an operation sequence t$t$ of length 2n$2n$. Just as Keine thinks she has finished, Yukari appears again and shuffles the order of t$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.

Cirno's Perfect Bitmasks Classroom Codeforces Solution

Patchouli's Magical Talisman Codeforces Solution

Manipulating History Codeforces Solution

The Enchanted Forest Codeforces Solution

Railway System Codeforces Solution

Sanae and Giant Robot Codeforces Solution

Input

Each test contains multiple test cases. The first line contains a single integer T$T$ (1≤T≤103$1\le T\le {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$n$ (1≤n<105$1\le n<{10}^5$) — the number of operations.

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

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

It is guaranteed that the total length of given strings (including ti$t_i$ and s$s$) over all test cases does not exceed 2⋅105$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.

Output

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