Поликарп придумал новую игру, в которую он хочет поиграть с вами. Он называет ее «Потерянная биграмма».
Биграмма слова — это последовательность двух подряд идущих в нем букв.
Например, слово «abbaaba» содержит биграммы «ab», «bb», «ba», «aa», «ab» и «ba».
Процесс игры следующий. Сначала Поликарп придумывает слово, состоящее только из строчных букв 'a' и 'b'. Затем он выписывает все его биграммы на доске в том же порядке, в котором они идут в строке. После этого он стирает одну из них с доски.
Наконец, Поликарп приглашает вас угадать, какое слово он загадывал.
Ваша цель — найти любое такое слово, что можно выписать все его биграммы и удалить одну так, чтобы полученная последовательность биграмм совпадала с той, которая получилась у Поликарпа.
Тесты сгенерированы таким образом, что ответ существует. Если существует несколько ответов, то выведите любой из них.
Выходные данные
На каждый набор входных данных выведите одно слово из \(n\) букв, каждая из них должна быть либо 'a', либо 'b'. Должно быть возможно выписать все его биграммы и удалить одну так, чтобы полученная последовательность биграмм совпадала с той, которая получилась у Поликарпа (которая дана во входных данных).
Тесты сгенерированы таким образом, что ответ существует. Если существует несколько ответов, то выведите любой из них.
Примечание
Первые два набора входных данных из примера получены из слова «abbaaba». Как приведено в условии, оно содержит биграммы «ab», «bb», «ba», «aa», «ab» и «ba».
В первом наборе входных данных удалена \(5\)-я биграмма.
Во втором наборе входных данных удалена \(2\)-я биграмма. Однако, такая последовательность могла быть получена и из слова «abaabaa». Оно содержит биграммы «ab», «ba», «aa», «ab», «ba» и «aa». Отсутствующая биграмма – \(6\)-я.
В третьем наборе входных данных все слова из «baa», «aab» and «aaa» — правильные ответы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
7
ab bb ba aa ba
7
ab ba aa ab ba
3
aa
5
bb ab bb
|
abbaaba
abaabaa
baa
bbabb
|