Suffix Game 2#5923
Ksyusha is playing a game involving strings.
She writes letters one by one on a sheet of paper. On the first step, she writes the letter s_1, on the second step s_2, and so forth. Ksyusha also has a string , which is used to calculate her score in the game.
Her score is determined 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 .
Ksyusha can stop writing letters at any point, but she must write at least one letter. Your task is to help her devise a strategy that minimizes her score in the game. In other words, find a string s_1s_2s_3 such that if Ksyusha writes the characters of this string, she will achieve the lowest possible score.
The first line contains the string (1 \leq |t| \leq 10^5). The string consists only of lowercase Latin letters.
Print the solution to the problem — the string . If there are multiple such strings, print the one that is smallest in lexicographical order.
Note: The string x = x_1x_2...x_p is lexicographically smaller than the string y = y_1y_2...y_q if either p < q and x_1 = y_1, x_2 = y_2, ..., x_p = y_p, or there exists a number (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.
Example 1