После того, как Алиса купила подписку на Congo Prime Video, она начала смотреть документальный фильм об археологических находках с острова Фактор на озере Лох Катрин в Шотландии. Археологи нашли книгу, возраст и происхождение которой неизвестны. Возможно Алиса сможет расшифровать ее?
В книжке записано только одно слово, которое состоит из символов «a», «b» и «c». Было замечено, что нет двух последовательных одинаковых символов. Так же было предположено, что в этой строке есть длинная подпоследовательность, которая читается слева направо так же, как и справа налево.
Помогите Алисе найти любую такую подпоследовательность, которая содержит как минимум половину (округленную вниз) символов из начальной строки. Обратите внимание, что вам не нужно максимизировать ее длину.
Строка \(a\) является подпоследовательностью \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов.
Выходные данные
Выведите палиндром \(t\), который является подпоследовательностью строки \(s\) и \(|t| \geq \lfloor \frac{|s|}{2} \rfloor\).
Если существует несколько решений, выведите любое из них. Обратите внимание, что вам не нужно максимизировать длину \(t\).
Если решения не существует, выведите «IMPOSSIBLE» (без кавычек).