Суфіксна гра (Hard)
Ксюша грає в гру з рядками.
Вона по черзі записує літери на аркуш паперу. На першому кроці вона записує літеру 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^5). Рядок t складається лише з малих латинських літер.
Вихідні дані
Виведіть відповідь на задачу — рядок s. Якщо таких рядків декілька, виведіть найменший у лексикографічному порядку.