B. Palindromic Feature
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Arkady is a huge fun of machine learning, he tries to apply it in every problem he works on. He believes in an ultimate magic power of this popular young part of computer science. That is why Arkady always invents new machine learning features to compute them for his favorite objects.

Let us recall that a string is called palindrome if it reads the same from the beginning to the end and vice versa, from the end to the beginning. For each string in his data base Arkady wants to compute its shortest substring that consists of at least two characters and is a palindrome. If there are several such string Arkday wants to pick lexicographical smallest one.

Input

The only line of the input contains a single string from Arkady's data base, that is a non-empty sequence of lowercase English letters. The length of this string is at least 2 and doesn't exceed 200 000 characters.

Output

Print the shortest substring of the input string that consists of at least two characters and is a palindrome. Do not forget that Arkady want to find lexicographical smallest possible such string.

Examples
Input
abac
Output
aba
Input
yandex
Output
-1
Note

We say that string a = a1a2... an is lexicographical smaller than string b = b1b2... bm if one the following is true:

  • if n < m and a1 = b1, a2 = b2, ..., an = bn, that is the first string is a prefix of the second string.
  • there exists such position 1 ≤ i ≤ min(n, m), that a1 = b1, a2 = b2..., ai - 1 = bi - 1 and ai < bi, that is the first string has a smaller character at the first position where the string differ.