Suffix Game#5912
Ksusha is playing a game with strings.
In this game, Ksusha writes letters one by one, in sequence, on a sheet. On the first step, she writes the letter s_1, on the second step, she writes s_2, and so on. 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 occurrences of the string s_1 in is added to her score. On the second step, the number of occurrences of the string s_1s_2 in is added, then on the third step the number of occurrences of s_1s_2s_3 in , and so forth. Initially, her score is .
Ksusha may stop writing letters at any moment. Your task is to help her choose a strategy that maximizes her score. In other words, determine the string s = s_1s_2 \dots s_n such that, if Ksusha writes its symbols in order, her total score will be as large as possible.
The first line contains the string (1 \leq |t| \leq 10^4). The string consists only of lowercase Latin letters.
Print the answer to the problem — the string . If there are multiple such strings with the same maximum score, print the lexicographically smallest one.
Example 1
A string x = x_1x_2\dots x_p is lexicographically smaller than a string y = y_1y_2\dots y_q, if either p < q and x_1 = y_1, x_2 = y_2, ..., x_p = y_p, or there exists an integer (r < p, r < q) such that x_1 = y_1, x_2 = y_2, ..., x_r = y_r, and x_{r+1} < y_{r+1}. The characters of the strings are compared by their ASCII codes.