404990: GYM101727 B Palindromic Feature
Description
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.
InputThe 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.
OutputPrint 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.
ExamplesInputabacOutput
abaInput
yandexOutput
-1Note
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.