Егор Кубратов очень огорчен задачами с codeforces и олимпиады Иннополиса, поэтому теперь он сам придумывает задачи и сам же их решает. Сегодня он придумал следующую задачу:
“Тандемный префикс – это подстрока, образованная конкатенацией двух непустых, не обязательно одинаковых префиксов строки и не являющаяся префиксом строки*. Вам необходимо найти длиннейший тандемный префикс данной строки. Если вариантов несколько, выведите тот, вхождение которого самое раннее. Если тандемного префикса не существует, то выведите -1”
*Имеется в виду, что тандемный префикс не является подстрокой, начинающейся в первом символе строки. То есть по составу букв он может являться каким-то префиксом, но только если начинается не в первой позиции. Например, в строке “aaa” подстрока [2;3] является тандемным префиксом.
Входные данные
В первой строке дана строка, состоящая из строчных латинских букв. Длина строки не превышает 105.
Выходные данные
Выведите ответ, если он существует. Иначе выведите -1.
Подстроки abca и abcab являются конкатенациями двух префиксов, но они сами являются префиксами, что противоречит определению тандемного префикса, поэтому aba – единственный тандемный префикс данной строки.
(с) Курбатов Е., 2017