Suffix Game (Hard)#5942
Ksusha is playing a game involving strings.
In this game, Ksusha writes letters sequentially on a sheet of paper. On the first step, she writes the letter s_1, on the second step s_2, and so forth. She also has a string , which is used to calculate her score in the game.
The scoring works as follows: On the first step, the number of times the string s_1 appears in is added to her score. On the second step, the number of times the string s_1s_2 appears in is added. On the third step, the number of times s_1s_2s_3 appears in is added, and so on. Initially, her score is .
Ksusha can stop writing letters whenever she chooses. Your task is to help her devise a strategy that maximizes her score. In other words, determine the string s_1s_2\dots s_n that, when written by Ksusha, yields the highest possible score.
The first line contains the string (1 \le |t| \le 10^5). The string consists solely of lowercase Latin letters.
Output the solution to the problem — the string . If there are multiple strings that yield the maximum score, output the lexicographically smallest one.
Example 1