Problem description

Dany jest ciąg literek, z których należy złożyć słowo jak w Scrabble’ach. Słowo jak słowo, w tym zadaniu nie musi ono pochodzić ze słownika, wystarczy, żeby było palindromem. Żeby było trochę trudniej – ma być ono najdłuższe, a spośród wielu takich najdłuższych słów, najmniejsze leksykograficznie.

Napisz program, który: wczyta ciąg dostępnych literek, wyznaczy najmniejsze leksykograficznie najdłuższe palindromiczne słowo, które można skonstruować z podanych literek i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (i jedynym) wierszu znajduje się niepusty ciąg małych liter alfabetu angielskiego – litery dostępne do konstrukcji słowa.

Wyjście

W pierwszym (i jedynym) wierszu wyjścia powinno się znaleźć utworzone słowo.

Ograniczenia

Długość ciągu wejściowego nie przekracza miliona znaków.

Przykład

scrabble

bab

tata

atta