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

После того, как Алиса купила подписку на Congo Prime Video, она начала смотреть документальный фильм об археологических находках с острова Фактор на озере Лох Катрин в Шотландии. Археологи нашли книгу, возраст и происхождение которой неизвестны. Возможно Алиса сможет расшифровать ее?

В книжке записано только одно слово, которое состоит из символов «a», «b» и «c». Было замечено, что нет двух последовательных одинаковых символов. Так же было предположено, что в этой строке есть длинная подпоследовательность, которая читается слева направо так же, как и справа налево.

Помогите Алисе найти любую такую подпоследовательность, которая содержит как минимум половину (округленную вниз) символов из начальной строки. Обратите внимание, что вам не нужно максимизировать ее длину.

Строка $$$a$$$ является подпоследовательностью $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов.

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

Первая строка содержит строку $$$s$$$ ($$$2 \leq |s| \leq 10^6$$$). Строка $$$s$$$ состоит только из символов «a», «b», «c». Гарантируется, что нет двух последовательных одинаковых символов.

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

Выведите палиндром $$$t$$$, который является подпоследовательностью строки $$$s$$$ и $$$|t| \geq \lfloor \frac{|s|}{2} \rfloor$$$.

Если существует несколько решений, выведите любое из них. Обратите внимание, что вам не нужно максимизировать длину $$$t$$$.

Если решения не существует, выведите «IMPOSSIBLE» (без кавычек).

Примеры
Входные данные
cacbac
Выходные данные
aba
Входные данные
abc
Выходные данные
a
Входные данные
cbacacacbcbababacbcb
Выходные данные
cbaaacbcaaabc
Примечание

В первом примере другими возможными ответами могут быть «cacac», «caac», «aca» и «ccc».