B. Фактор палиндромности
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аркадий — большой фанат использования машинного обучения в любой задаче. Он верит в безграничную силу волшебства этой популярной молодой науки. Именно поэтому Аркадий постоянно постоянно придумывает всё новые и новые факторы, которые можно вычислить для различных объектов.

Напомним, палиндромом называется строка, которая одинаково читается от начала к концу и от конца к началу. Для каждой строки в своей базе данных Аркадий хочет найти самую короткую её подстроку, состоящую хотя бы из двух символов и являющуюся палиндромом. Если таких подстрок несколько, Аркадий хочет выбрать лексикографически минимальную.

Входные данные

В единственной строке входных данных записана одна строка из базы Аркадия — непустая последовательность строчных букв английского алфавита. Длина строки составляет не менее 2 и не превосходит 200 000 символов.

Выходные данные

Выведите минимальную по длине подстроку строки из входных данных, состоящую хотя бы из двух символов и являющуюся палиндромом. Напомним, что среди всех таких строк Аркадий хочет найти лексикографически минимальную.

Примеры
Входные данные
abac
Выходные данные
aba
Входные данные
yandex
Выходные данные
-1
Примечание

Говорят, что строка a = a1a2... an лексикографически меньше строки b = b1b2... bm если верно одно из двух условий:

  • либо n < m и a1 = b1, a2 = b2, ..., an = bn, то есть первая строка является префиксом второй;
  • либо есть такая позиция 1 ≤ i ≤ min(n, m), что a1 = b1, a2 = b2..., ai - 1 = bi - 1 и ai < bi, то есть, в первой позиции, в которой строки различаются, в первой строке стоит меньшая буква.