404990: GYM101727 B Palindromic Feature

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.

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.

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.

abac

aba

yandex

-1

We say that string a = a₁a₂... a_n is lexicographical smaller than string b = b₁b₂... b_m if one the following is true:

• if n < m and a₁ = b₁, a₂ = b₂, ..., a_n = b_n, that is the first string is a prefix of the second string.
• there exists such position 1 ≤ i ≤ min(n, m), that a₁ = b₁, a₂ = b₂..., a_i - 1 = b_i - 1 and a_i < b_i, that is the first string has a smaller character at the first position where the string differ.