Суфіксна гра (Hard)#5942
Ксюша грає в гру з рядками.
Вона по черзі записує літери на аркуш паперу. На першому кроці вона записує літеру s_1, на другому — s_2, і так далі. У Ксюші також є рядок , який використовується для підрахунку очок, зароблених у грі.
Очки нараховуються так: на першому кроці додається кількість входжень рядка s_1 у . На другому кроці додається кількість входжень рядка s_1s_2 у . На третьому кроці — кількість входжень рядка s_1s_2s_3 у , і так далі. Спочатку кількість очок дорівнює .
Ксюша може в будь-який момент зупинити записування літер. Допоможіть їй обрати стратегію, яка максимізує кількість очок у грі. Іншими словами, знайдіть такий рядок s_1s_2\dots s_n, що якщо Ксюша буде записувати символи цього рядка, вона отримає максимально можливу кількість очок.
У першому рядку задано рядок (1 \leq |t| \leq 10^5). Рядок складається лише з малих латинських літер.
Виведіть відповідь на задачу — рядок . Якщо таких рядків декілька, виведіть найменший у лексикографічному порядку.
Приклад 1