404178: GYM101445 B Мысли о прекрасном

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

Маленький Пафнутий недавно выучил буквы. Теперь он радостно пишет их в ряд в тетради. Написав достаточно большую строку, Пафнутий задумался о прекрасном – а достаточно ли красива его строка? Еще немного помедлив, он понял, что считает строку красивой, если она имеет вид a₁a₂a₂a₃a₃a₃... a_n... a_n. Например, строки a, abbccc, aaaaaa, xaabbbbbbb – красивые, а строки abbcc, aa, bbaaa – нет. Теперь Пафнутий просит Вас помочь найти в его строке красивую подстроку максимальной длины.

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

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

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

Выведите искомую подстроку.

ПримерыВходные данные

abbccc

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

abbccc

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

misis

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

m

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

missiiis

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

issiii

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

aaaaaaa

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

aaaaaa