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