Қилы тағдырымен бірге Надекода кіші әріптерден тұратын $s$ жолы бар. Оның ең басты тілегі — келесі шарттар орындалатын $t$ жолын құрастыру:
- $t$ жолы $s$ жолын ішкі тізбек ретінде қамтымайды.
- $s$ жолының $s$-пен беттеспейтін әрбір ішкі тізбегі $t$ жолында ішкі тізбек ретінде қамтылған.
Оған мүмкін болатын ең қысқа ұзындықтағы $t$ жолын табуға көмектесіңіз. Егер мұндай жолдар бірнешеу болса, кез келгенін шығаруға рұқсат етіледі.
Кіріс деректер
Кіріс деректерінің жалғыз жолында $s$ жолы ($2 \le |s| \le 10^6$) — Надеконың жолы берілген. $s$ тек кіші әріптерден тұратынына кепілдік беріледі.
Шығыс деректер
Жалғыз жолда есептің шарттарын қанағаттандыратын ең қысқа ұзындықтағы кез келген $t$ жолын шығарыңыз.
Мысалдар
Кіріс деректер 1
aaaa
Шығыс деректер 1
aaa
Кіріс деректер 2
bba
Шығыс деректер 2
bab
Ескертпе
Екінші мысалда bab жолы ішкі тізбек ретінде bb, ba, a, b жолдарын қамтиды, бірақ bba жолын қамтымайды. Сондай-ақ ұзындығы $2$ болатын дұрыс тізбекті құру мүмкін емес екені анық, сондықтан bab мүмкін жауап болып табылады.