Суфіксна гра 2
Дівчинка Ксюша грає в гру з рядками.
Ксюша по черзі виписує літери на аркушик. На першому кроці вона виписує літеру s_1, на другому — s_2, і так далі. Також у Ксюші є рядок t, за допомогою якого обчислюється кількість очок, які вона заробляє в грі.
Кількість очок, які заробляє Ксюша, обчислюється наступним чином. На першому кроці до неї додається кількість входжень рядка s_1 в t. На другому кроці додається кількість входжень рядка s_1s_2 в t. На третьому кроці — кількість входжень s_1s_2s_3 в t. І так далі. Спочатку кількість очок дорівнює 0.
Ксюша може в будь-який момент зупинитися, але вона повинна виписати хоча б одну літеру. Допоможіть їй обрати стратегію, яка мінімізує кількість очок, отриманих у грі. Іншими словами, знайдіть такий рядок s_1s_2s_3, що якщо Ксюша буде виписувати символи цього рядка, вона отримає мінімально можливу кількість очок.
Вхідні дані
У першому рядку записано рядок t (1 ≤ |t| ≤ 10^5). Рядок 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 кодами.