Девочка Ксюша играет в игру со строками. Ксюша по очереди, одну за одной, выписывает буквы на листочек. На первом шаге она выписывает букву \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} коды.