Suffix Game 2

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 (t), 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 (t) is added to her score. On the second step, the number of times the string (s_1s_2) appears in (t) is added. On the third step, the number of times (s_1s_2s_3) appears in (t) is added, and so on. Initially, her score is (0).

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.

Input

The first line contains the string (t) ((1 $\le$ |t| $\le$ 10^5)). The string (t) consists only of lowercase Latin letters.

Output

Print the solution to the problem — the string (s). 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) ((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.

Examples