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