Подпоследовательность - это часть последовательности, полученная путём удаления нуля или более символов в строке. Палиндромом является строка, которая при чтении слева направо, читается так же, как и когда читать справа налево. В заданной строке найдите самую длинную палиндромную подпоследовательность. Если есть много вариантов ответов, то вывести тот, который является лексикографически наименьшим.

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

Содержит несколько тестов, каждый из которых размещён в отдельной строке. Наибольшая длина строки равна 1000. Все символы в строках находятся в диапазоне от 'a' до 'z'.

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

Для каждой строки вывести лексикографически наименьшую максимальную палиндромную подпоследовательность.