Codeforces Round 796 (Div. 2) |
---|
Закончено |
Keine обладает способностью управлять историей.
История Gensokyo представляет собой строку $$$s$$$ начальной длины $$$1$$$. Чтобы исправить хаос, вызванный Yukari, ей нужно выполнить следующие операции $$$n$$$ раз, в $$$i$$$-й раз:
Обратите внимание, что если $$$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$$$. Все заданные строки состоят только из строчных латинских букв.
Гарантируется, что исходная строка существует. Можно показать, что исходная строка уникальна.
Для каждого теста выведите исходную строку в одной строке.
22aabbcdacd3zaaaayakumoranyakumoran
a z
В первом наборе входных данных изначально $$$s$$$ равно «a».
Таким образом, последняя строка будет «acd», а $$$t=[$$$«a», «ab», «b» , «cd»$$$]$$$ перед перемешиванием.
Во втором наборе входных данных изначально $$$s$$$ равно «z».
Таким образом, последняя строка будет «yakumoran», а $$$t=[$$$«z», «aa», «a» , «ran», «a», «yakumo»$$$]$$$ перед перемешиванием.
Название |
---|