Суфіксна гра
Дівчинка Ксюша грає у гру з рядками.
Ксюша по черзі, одну за одною, виписує букви на аркуш. На першому кроці вона виписує букву s_1, на другому — s_2, і так далі. Також у Ксюши є рядок t, за допомогою якого рахується кількість очок, зароблених Ксюшею у грі.
Кількість очок, які заробить Ксюша, рахується наступним чином. На першому кроці до них додається кількість входжень рядка s_1 у t. На другому кроці до них додається кількість входжень рядка s_1s_2 у t. На третьому кроці — кількість входжень s_1s_2s_3 у t. І так далі. Спочатку кількість очок дорівнює 0.
Ксюша у довільни момент часу може припинити виписувати букви. Допоможіть їй вибрати стратегію, яка максимізує кількість очок, отриманих у грі. Іншими словами, знайдіть такий рядок s_1s_2...s_n, що якщо Ксюша буде виписувати символи цього рядкаи, вона отримає максимально можливу кількість очок.
Вхідні дані
У першому рядку записано рядок t (1 ≤ |t| ≤ 10^4). Рядок t складається лише з маленьких латинських букв.
Вихідні дані
Виведіть відповідь до задачі — рядок s. Якщо таких рядків декілька, виведіть мінімальний у лексикографічному порядку.
Примітка. Рядок x = x_1x_2...x_p лексикографічно менший рядкаи y = y_1y_2...y_q, якщо або p < q и x_1 = y_1, x_2 = y_2, ..., x_p = y_p, або існує таке число r (r < p, r < q), що x_1 = y_1, x_2 = y_2, ..., x_r = y_r и x_{r+1} < y_{r+1}. Символи рядків порівнюються як їхні ASCII коди.