Маленький Пафнутий недавно выучил буквы. Теперь он радостно пишет их в ряд в тетради. Написав достаточно большую строку, Пафнутий задумался о прекрасном – а достаточно ли красива его строка? Еще немного помедлив, он понял, что считает строку красивой, если она имеет вид a1a2a2a3a3a3... an... an. Например, строки a, abbccc, aaaaaa, xaabbbbbbb – красивые, а строки abbcc, aa, bbaaa – нет. Теперь Пафнутий просит Вас помочь найти в его строке красивую подстроку максимальной длины.
В единственной строке входного файла задана непустая строка s длиной не более 105 символов, состоящая из строчных букв латинского алфавита.
Выведите искомую подстроку.
abbccc
abbccc
misis
m
missiiis
issiii
aaaaaaa
aaaaaa
