C. Управление историей
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Keine обладает способностью управлять историей.

История Gensokyo представляет собой строку $$$s$$$ начальной длины $$$1$$$. Чтобы исправить хаос, вызванный Yukari, ей нужно выполнить следующие операции $$$n$$$ раз, в $$$i$$$-й раз:

  • Она выбирает непустую подстроку $$$t_{2i-1}$$$ из $$$s$$$.
  • Она заменяет $$$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 получил окончательную строку и последовательность операций $$$t$$$ длины $$$2n$$$. Keine думал, что уже решил задачу, но появился Yukari и перемешал порядок $$$t$$$. Что еще хуже, Keine забыл изначальную историю.

Помогите Keine найти изначальную историю Gensokyo!

Напомним, что подстрока — это последовательность последовательных символов строки. Например, для строки «abc» ее подстроки: «ab», «c», «bc» и некоторые другие . Но следующие строки не являются его подстрокой: «ac», «cba», «acb».

Взломы

Вы не можете делать взломы в этой задаче.

Входные данные

Первая строка содержит единственное целое число $$$T$$$ ($$$1 \leq T \leq 10^3$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n < 10 ^ 5$$$) — количество операций.

Следующие $$$2n$$$ строк содержат одну непустую строку $$$t_{i}$$$ — $$$i$$$-ю строку перетасованной последовательности $$$t$$$.

Следующая строка содержит одну непустую строку $$$s$$$ — итоговую строку.

Гарантируется, что суммарная длина заданных строк (включая $$$t_i$$$ и $$$s$$$) по всем наборам входных данных не превосходит $$$2 \cdot 10 ^ 5$$$. Все заданные строки состоят только из строчных латинских букв.

Гарантируется, что исходная строка существует. Можно показать, что исходная строка уникальна.

Выходные данные

Для каждого теста выведите исходную строку в одной строке.

Пример
Входные данные
2
2
a
ab
b
cd
acd
3
z
a
a
aa
yakumo
ran
yakumoran
Выходные данные
a
z
Примечание

В первом наборе входных данных изначально $$$s$$$ равно «a».

  • В первой операции Keine выбирает «a» и заменяет его на «ab». $$$s$$$ становится «ab».
  • Во второй операции Keine выбирает «b» и заменяет его на «cd». $$$s$$$ становится «acd».

Таким образом, последняя строка будет «acd», а $$$t=[$$$«a», «ab», «b» , «cd»$$$]$$$ перед перемешиванием.

Во втором наборе входных данных изначально $$$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»$$$]$$$ перед перемешиванием.