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».
Взломы
Вы не можете делать взломы в этой задаче.
Выходные данные
Для каждого теста выведите исходную строку в одной строке.
Примечание
В первом наборе входных данных изначально \(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»\(]\) перед перемешиванием.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2
a
ab
b
cd
acd
3
z
a
a
aa
yakumo
ran
yakumoran
|
a
z
|