Secret Word

Problem Background

UVA 12467

Problem Description

Given a string $s$, find the longest "secret word" of $s$. A string $p$ is a "secret word" if:

• $p$ is a substring of $s$ ($p$ may equal $s$);
• the reverse of $p$ is a prefix of $s$.

Output one line with the string $p$ you find.

Input Format

One line with a string $s$.

Output Format

Output one line with a string, the answer.

Sample Input

listentothesilence

Sample Output

sil

Constraints

For all data: $1 \leq |s| \leq 10^5$, and $s$ consists only of lowercase letters.