Паліндромна підпослідовність

Підпослідовність - це частина послідовності, отримана шляхом видалення нуля або більше символів у рядку. Паліндромом є рядок, який при читанні зліва праворуч, читається так само, як і коли читати зправа ліворуч. Отримавши рядок, знайти найдовшу паліндромну підпослідовність. Якщо є декілька варіантів відповіді, то вивести той, який є лексикографічно найменшим.

Вхідні дані

Складаються з декількох тестів, кожен з яких розташований в окремому рядку.Найбільша довжтна рядка дорівнює 1000. Усі символи в рядках знаходяться в діапазоні від 'a' до 'z'.

Вихідні дані

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

Приклади