Суффиксная игра (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. Если таких строк несколько, выведите минимальную в лексикографическом порядке.